Submission #1230375

#TimeUsernameProblemLanguageResultExecution timeMemory
1230375ByeWorldSum Zero (RMI20_sumzero)C++20
0 / 100
11 ms19776 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+10; const int SQRT = 450; const int MOD = 998244353; const int LOG = 9; int sum(int a, int b){ return (a+MOD+b)%MOD; } void chsum(int &a, int b){ a = (a+MOD+b)%MOD; } int mul(int a, int b){ return (a*b)%MOD; } void chmul(int &a, int b){ a = (a*b)%MOD; } void chmn(auto &a, auto b){ a = min(a, b); } void chmx(auto &a, auto b){ a = max(a, b); } int n, pr[MAXN], q, ba[MAXN], ans[MAXN]; int anc[MAXN][LOG], dp[MAXN]; unordered_map<int,int> ma; vector<int> vec[MAXN]; vector<pii> que[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++){ if(pr[i] != 0 && ma[ pr[i] ] == 0){ ba[i] = -1; ma[pr[i]] = i; continue; } ba[i] = ma[ pr[i] ]; vec[ ba[i]+1 ].pb(i); ma[pr[i]] = i; } int mn = n+1; anc[n+1][0] = n+1; for(int i=n; i>=1; i--){ for(auto in : vec[i]) chmn(mn, in); dp[i] = mn; // cout << i << ' ' << mn << " mn\n"; anc[i][0] = mn; } for(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; for(int x=1; x<=q; x++){ int a, b; cin>>a>>b; que[a].pb({b, x}); } for(int i=n; i>=1; i--){ mn = dp[i]; if(mn==n+1) continue; for(auto [r, idx] : que[i]){ // lift sampe kurang dari r int tot = 0, nw = i; // cout << idx<<' '<<nw << " idx\n"; for(int j=LOG-1; j>=0; j--){ if( anc[nw][j] <= r){ // cout << nw << ' ' << anc[nw][j] << " anc\n"; nw = anc[nw][j]+1; tot += (1<<j); } } ans[idx] = tot; } } for(int X=1; X<=q; X++) cout << ans[X] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...