oj.uz

Submission #942651

# Submission time Handle Problem Language Result Execution time Memory
942651 2024-03-11T02:27:10 Z huutuan Sum Zero (RMI20_sumzero) C++14
100 / 100
 622 ms 16832 KB 
#include<bits/stdc++.h>

using namespace std;

using ll=long long;
const int N=4e5+10, LG=9;
int n;
int *a, *nxt;
pair<ll, int> *pf;
int jump[LG][N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   a=new int[n+1];
   nxt=new int[n+1];
   pf=new pair<ll, int>[n+1];
   memset(nxt, -1, (n+1)*(sizeof(int)));
   pf[0]={0, 0};
   for (int i=1; i<=n; ++i) cin >> a[i], pf[i]={pf[i-1].first+a[i], i};
   sort(pf, pf+n+1);
   for (int i=0; i<=n; ++i){
      int j=i;
      while (j<n && pf[j+1].first==pf[i].first) ++j;
      for (int k=i; k<j; ++k) nxt[pf[k].second+1]=pf[k+1].second;
      i=j;
   }
   delete[] a;
   delete[] pf;
   int mn=n+1;
   jump[0][n+1]=n+1;
   for (int i=n; i>=0; --i){
      jump[0][i]=mn;
      if (nxt[i]!=-1) mn=min(mn, nxt[i]);
   }
   delete[] nxt;
   for (int k=1; k<LG; ++k) for (int i=0; i<=n+1; ++i) jump[k][i]=jump[k-1][jump[k-1][i]];
   int q; cin >> q;
   while (q--){
      int x, y; cin >> x >> y;
      int ans=0, cur=x-1;
      for (int i=LG-1; i>=0; --i){
         while (jump[i][cur]<=y){
            cur=jump[i][cur];
            ans+=1<<i;
         }
      }
      cout << ans << '\n';
   }
   return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 61 ms 13608 KB Output is correct
8 Correct 44 ms 13664 KB Output is correct
9 Correct 63 ms 13588 KB Output is correct
10 Correct 60 ms 13616 KB Output is correct
11 Correct 44 ms 13676 KB Output is correct
12 Correct 64 ms 13772 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 61 ms 13608 KB Output is correct
8 Correct 44 ms 13664 KB Output is correct
9 Correct 63 ms 13588 KB Output is correct
10 Correct 60 ms 13616 KB Output is correct
11 Correct 44 ms 13676 KB Output is correct
12 Correct 64 ms 13772 KB Output is correct
13 Correct 622 ms 16284 KB Output is correct
14 Correct 225 ms 16164 KB Output is correct
15 Correct 573 ms 16808 KB Output is correct
16 Correct 543 ms 16692 KB Output is correct
17 Correct 227 ms 16020 KB Output is correct
18 Correct 580 ms 16832 KB Output is correct