Submission #1203104

#TimeUsernameProblemLanguageResultExecution timeMemory
1203104al95ireyizSum Zero (RMI20_sumzero)C++20
100 / 100
292 ms21448 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 er erase #define sc second #define in insert #define ll int #define pb push_back #define vll vector<ll> #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; const ll lg = 9; ll a[maxn], up[maxn][lg]; pll p[maxn]; void _(ll tt){ cin>>n; ll pr = 0, pos = n + 1; up[0][0] = up[n+1][0] = n + 1; for(ll i = 1; i <= n; i ++) cin>>a[i], pr += a[i], p[i] = {pr, i}, up[i][0] = n + 1; sort(p, p + n + 1); for(ll i = 0; i <= n; i ++){ if(p[i].fr == p[i - 1].fr) up[p[i - 1].sc][0] = p[i].sc; } for(ll i = n; i >= 0; i --){ if(up[i][0] == 0) up[i][0] = 0; up[i][0] = min(up[i][0], up[i+1][0]); } for(ll i = 1; i < lg; i ++){ for(ll j = 0; j <= n + 1; j ++){ up[j][i] = up[up[up[up[j][i-1]][i-1]][i-1]][i-1]; // 4^i-th parent } } cin>>m; for(ll i = 1, l, r; i <= m; i ++){ cin>>l>>r; l --; ll cv = 0; for(ll i = lg - 1, pw = 65536; i >= 0; i --, pw /= 4){ if(up[l][i] <= r and up[l][i] != 0){ cv += pw; l = up[l][i]; } if(up[l][i] <= r and up[l][i] != 0){ cv += pw; l = up[l][i]; } if(up[l][i] <= r and up[l][i] != 0){ cv += pw; l = up[l][i]; } if(up[l][i] <= r and up[l][i] != 0){ cv += pw; 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"; }

Compilation message (stderr)

sumzero.cpp:21:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const ll INFL = 1e18;
      |                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...