Submission #1203030

#TimeUsernameProblemLanguageResultExecution timeMemory
1203030al95ireyizSum Zero (RMI20_sumzero)C++20
22 / 100
91 ms27716 KiB
//*** Bismillah ***// #pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector") #include <bits/stdc++.h> using namespace std; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif #define fr first #define sc second #define ll long long #define pb push_back #define pll pair<ll,ll> #define len(x)(ll)x.size() #define all(x)x.begin(),x.end() const ll INF = 1e9; const ll INFL = 1e18; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll maxn = 4e5+5; ll n,m,k=0; ll a[maxn], up[maxn][30]; map<ll, ll> mp; void _(ll tt){ cin>>n; ll pr = 0, pos = n + 1; for(ll i = 1; i <= n; i ++) cin>>a[i], pr += a[i]; for(ll i = n; i >= 0; i --){ if(mp.count(pr)) pos = min(pos, mp[pr]); up[i][0] = pos; mp[pr] = i; pr -= a[i]; } mp.clear(); up[n+1][0] = n + 1; for(ll i = 1; i < 30; i ++){ for(ll j = 0; j <= n + 1; j ++){ up[j][i] = up[up[j][i-1]][i-1]; } } cin>>m; for(ll i = 1, l, r; i <= m; i ++){ cin>>l>>r; l --; ll cv = 0; for(ll i = 29; i >= 0; i --){ if(up[l][i] <= r and up[l][i] != 0){ cv += 1ll << i; l = up[l][i]; } } cout<<cv<<'\n'; } } signed main(){ ll tm=clock(); cin.tie(0)->sync_with_stdio(0); ll t=1; // cin>>t; for(ll tt=1;tt<=t;tt++){ _(tt); } cerr<<"\n\033[1;31mTime: \033[1;30m" \ <<(double)(clock()-tm)/1000000<<"\033[1;32m seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...