Submission #1242011

#TimeUsernameProblemLanguageResultExecution timeMemory
1242011AMnuSum Zero (RMI20_sumzero)C++20
61 / 100
214 ms35724 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,int> pli; const int MAXN = 4e5+5; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; cin >> N; int par[N+2], sub[N+2], big[N+2], rot[N+2], dep[N+2]; pli P[N+2]; vector <int> ch[N+2]; for (int i=0;i<=N+1;i++) { par[i] = N+1; big[i] = N+2; rot[i] = -1; sub[i] = 0; } P[0] = {0,0}; for (int i=1;i<=N;i++) { cin >> P[i].fi; P[i].fi += P[i-1].fi; P[i].se = i; } sort(P,P+N+1); for (int i=1;i<=N;i++) { if (P[i].fi == P[i-1].fi) { par[P[i-1].se] = P[i].se; } } dep[N+1] = 0; for (int i=N;i>=0;i--) { par[i] = min(par[i],par[i+1]); dep[i] = dep[par[i]]+1; } for (int i=0;i<=N;i++) { sub[i]++; sub[par[i]] += sub[i]; if (sub[i] > sub[big[par[i]]]) { big[par[i]] = i; } } for (int i=N+1;i>=0;i--) { if (rot[i] != -1) continue; int j = i; while (j != N+2) { rot[j] = i; ch[i].push_back(j); j = big[j]; } reverse(ch[i].begin(),ch[i].end()); } int Q; cin >> Q; while (Q--) { int L, R; cin >> L >> R; L--; int ans = dep[L]; while (par[rot[L]] <= R) { L = par[rot[L]]; } int x = upper_bound(ch[rot[L]].begin(),ch[rot[L]].end(),R) - ch[rot[L]].begin() - 1; x = ch[rot[L]][x]; cout << ans - dep[x] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...