Untitled

unknown
c_cpp
24 days ago
3.8 kB
2
Indexable
Never
```#include <bits/stdc++.h>

#define ll long long
#define II pair<int, int>
#define fs first
#define sc second
#define endl '\n'

#define mp(x, y) make_pair(x, y)
#define sz(x) ((int) (x.size()))
#define forlr(i, l, r) for(int i = l; i <= r; ++i)
#define forrl(i, r, l) for(int i = r; i >= l; --i)
#define show(v) for(auto i : v) cout << i << " "; cout << endl;
#define showlr(v, l, r) for (int i = l; i <= r; i++) cout << v[i] << " "; cout << endl;
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end());

const long long LINF = 1ll << 60;
const int INF = 1 << 30;
const int N = 2e5 + 5;

using namespace std;

int n, k;
int a[N], pre[N], L[N], R[N];
vector<int> divs[N];

namespace BRUTE {
void solve() {
int ans = 0;
forlr(i, 1, n) {
int M = INF, S = 0;
forlr(j, i, n) {
M = min(M, a[j]);
S += a[j];
int v = __gcd(M, S);
if(M + S == v * k) ans++;
}
}

cout << ans << endl;
}
}

namespace FULL {

int ans = 0;

inline void dnc(int l, int r) {
if(l == r) return;

int mid = (l + r) >> 1;

int mn = mid + 1;
forlr(i, mid + 1, r) {

if(a[i] < a[mn]) mn = i;

int Left = max(l, L[mn]), Right = mid;

for(int v : divs[a[mn]]) {
if(Left > Right) break;

int sum = a[mn] / v * (k - v);
int x = lower_bound(pre + Left - 1, pre + Right - 1, pre[i] - sum) - pre;

Right = x;
if(pre[i] - pre[x] == sum) ans++;
else Right++;
}
}

mn = mid;

forrl(i, mid, l) {

if(a[i] < a[mn]) mn = i;

int Left = mid + 1, Right = min(r, R[mn]);

for(int v : divs[a[mn]]) {
if(Left > Right) break;

int sum = a[mn] / v * (k - v);
int x = lower_bound(pre + Left, pre + Right, pre[i - 1] + sum) - pre;

Left = x;
if(pre[x] - pre[i - 1] == sum) ans++;
}
}

dnc(l, mid);
dnc(mid + 1, r);
}

void solve() {
dnc(1, n);
cout << ans << endl;
}
}

inline void create_divisors() {
forrl(i, k / 3, 1) {
if(__gcd(i, k - i) != 1) continue;
for(int j = i; j <= 100000; j += i) {
divs[j].push_back(i);
}
}
}

inline void show_divisors() {
int mx = 0;
forlr(i, 1, 100000) {
if(sz(divs[i]) > mx) {
mx = sz(divs[i]);
cout << i << " " << mx << endl;
}
}
}

inline void create_monotonic_stacks() {
stack<int> st;

forlr(i, 1, n) {
while(!st.empty() && a[st.top()] >= a[i]) st.pop();
L[i] = st.empty() ? 1 : st.top() + 1;
st.push(i);
}

while(!st.empty()) st.pop();

forrl(i, n, 1) {
while(!st.empty() && a[st.top()] > a[i]) st.pop();
R[i] = st.empty() ? n : st.top() - 1;
st.push(i);
}
}

int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

// freopen("A.INP", "r", stdin);
// freopen("A.OUT", "w", stdout);

cin >> n >> k;

forlr(i, 1, n) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}

create_monotonic_stacks();
create_divisors();
// show_divisors();

FULL::solve();
// BRUTE::solve();

return 0;
}```