Submission #1230395

#TimeUsernameProblemLanguageResultExecution timeMemory
1230395ByeWorldSum Zero (RMI20_sumzero)C++20
61 / 100
1097 ms21804 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") // #define int long long #define ll long long #define se second #define fi first #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; typedef pair<int,int> pii; typedef pair<pii,pii> ipii; const int MAXN = 4e5+2; const int LOG = 7; int n, pr[MAXN], q; int anc[MAXN][LOG]; unordered_map<int,int> ma; int te[MAXN]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i=1; i<=n; i++){ int a; cin>>a; pr[i] = pr[i-1]+a; } ma[0] = 0; for(int i=1; i<=n; i++) te[i] = n+1; for(int i=1; i<=n; i++){ if(pr[i] != 0 && ma[ pr[i] ] == 0){ ma[pr[i]] = i; continue; } te[ ma[pr[i]]+1 ] = min(te[ ma[pr[i]]+1 ], i); ma[pr[i]] = i; } int mn = n+1; anc[n+1][0] = n+1; for(int i=n; i>=1; i--){ mn = min(mn, te[i]); // cout << i << ' ' << mn << " mn\n"; anc[i][0] = mn; } for(short int j=1; j<LOG; j++){ for(int i=1; i<=n+1; i++){ if(anc[i][j-1] >= n){ anc[i][j] = n+1; continue; } anc[i][j] = anc[ anc[i][j-1]+1 ][j-1]; } } cin>>q; while(q--){ int a, b; cin>>a>>b; // lift sampe kurang dari r int tot = 0, nw = a; // cout << idx<<' '<<nw << " idx\n"; for(short int j=LOG-1; j>=0; j--){ while( anc[nw][j] <= b){ // cout << nw << ' ' << anc[nw][j] << " anc\n"; nw = anc[nw][j]+1; tot += (1<<j); } } cout << tot << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...