Submission #1242022

#TimeUsernameProblemLanguageResultExecution timeMemory
1242022hynmjSum Zero (RMI20_sumzero)C++20
0 / 100
3 ms1604 KiB
//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~ #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #define rep1(n) for(ll i=0; i<(ll)(n); ++i) #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i) #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i) #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c)) #define cut4(a,b,c,d,e,...) e #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define per1(n) for(ll i=((ll)n)-1; i>=0; --i) #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i) #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i) #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c)) #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) #define ll long long #define ln cout<<endl #define int long long #define Code ios_base::sync_with_stdio(0); #define by cin.tie(NULL); #define Hayan cout.tie(NULL); #define append push_back #define all(x) (x).begin(),(x).end() #define allr(x) (x).rbegin(),(x).rend() #define vi vector<int> #define ret(x) {cout<<x;return;} #define ui map<int,int> #define pi pair<int,int> #define ff first #define ss second using namespace std; template <typename T> using v = vector<T>; const int INF = 1e18, MOD = 1e9+7, N = 4e5+7; vi primes; int seen[N+1]; int st[N][22]; void solve() { int q,n, k, e, m, ans = 0; cin >> n ; vi a(n); rep(n) { cin >> e;a[i]=e; } map<int,vi> graph; vi pref(n+1,0); for (int i=1;i<=n;i++) { pref[i]+=pref[i-1] + a[i-1]; } rep(n+2)st[i][0]=n+1; map<int,int> last; last[0] = n; for (int i=n;i>=0;i--) { if (last[pref[i]]!=0) st[i][0] = last[pref[i]]; last[pref[i]]= i; } per(n) st[i][0]=min(st[i][0],st[i+1][0]); for (int p=1;p<22;p++) { for (int i=0;i<=n+1;i++) { st[i][p]=st[st[i][p-1]][p-1]; } } int l,r; cin >>q; rep(q) { cin >> l >> r; ans=0; l--; // cout << l <<" "; // cout << endl; for (int i=20;i>=0;i--) { if (st[l][i]<=r) { // cout << "jumped "<<(1ll<<i)<< " steps ahead"<< endl; // cout << l <<" "; l = st[l][i]; // cout << l <<" "; // l++; ans+=(1ll<<i); // cout<< " ans = "<< ans << endl; // cout << endl; } } cout <<ans << " "; } // rep(n+1)cout << st[i][0]<< " "; // ln; // rep(n+1)cout << st[i][1]<< " "; // cout << ans; // cout << a.size(); // for (auto i: next){cout << i << " ";} } signed main(){ Code by Hayan int ans=1; //cout<<setprecision(1000); // cin>>ans; rep(ans){ // cout << "Case #" << i+1 << ": "; solve();ln;}}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...