Submission #753417

#TimeUsernameProblemLanguageResultExecution timeMemory
753417lukameladzeSum Zero (RMI20_sumzero)C++14
0 / 100
4 ms2132 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <int, int> #define pb push_back const int N = 4e5 + 5, inf = 1e9; int t, n, a[N],par[N][5],nxt[N]; long long pr[N]; map <long long, int> mp; int tree[N]; void upd(int idx, int val) { for (int i = idx; i > 0; i -= i&(-i)) tree[i] = min(tree[i], val); } int getmn(int idx) { // suffix query int pas = n + 1; for (int i = idx; i < N; i += i&(-i)) pas = min(pas, tree[i]); return pas; } main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for (int i = 1; i <= n; i++) { cin>>a[i]; pr[i] = pr[i - 1] + a[i]; nxt[i] = -1; } mp[pr[0]] = 0; for (int i = 1; i <= n; i++) { if (mp[pr[i]] != 0 || pr[i] == 0) { nxt[mp[pr[i]] + 1] = i; } mp[pr[i]] = i; } int mn = inf; vector <pii> v; for (int i = n; i >= 1; i--) { if (nxt[i] == -1) continue; if (mn <= nxt[i]) continue; v.pb({i, nxt[i]}); mn = min(mn, nxt[i]); } sort(v.begin(), v.end()); // if (l[i] > l[j]) ---> r[i] > r[j] int m = v.size(); for (int i = 1; i < N; i++) tree[i] = n + 1; for (int i = (int)v.size() - 1; i >= 0; i--) { par[i + 1][0] = getmn(v[i].s + 1); upd(v[i].f, i + 1); } for (int j = 1; j <= 4; j++) { for (int i = 1; i <= m; i++) { int cur = i; for (int it = 1; it <= 4; it++) { if (par[cur][j - 1] == n + 1) { cur = n + 1; break; } cur = par[par[cur][j - 1]][j - 1]; } par[i][j] = cur; } } int q; cin>>q; while (q--) { int le, ri; cin>>le>>ri; int st_idx = getmn(le); if (st_idx == n + 1 || v[st_idx - 1].f > ri) { cout<<0<<"\n"; continue; } int cur = st_idx; int ans = 0; for (int i = 4; i >= 0; i--) { for (int it = 1; it <= 4; it++) { if (par[cur][i] != n + 1 && v[par[cur][i] - 1].f <= ri) cur = par[cur][i], ans += (1<<(4*i)); } } if (v[cur - 1].s <= ri) ans++; cout<<ans<<"\n"; } }

Compilation message (stderr)

sumzero.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...