Submission #1119931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119931		NintsiChkhaidze	Sum Zero (RMI20_sumzero)	C++17	100 / 100	769 ms	19052 KiB

sumzero

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 4e5 + 1;
int ans[N] , lst[N] , e[N], l[N], r[N];
unordered_map<LL , int> nt;
 
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n;
   cin >> n;
   LL sum = 0;
  
   int t = -1;
  for(int i = 1;i <= n; i++)
      cin >> ans[i];
 
   for(int i = 0;i <= n; i++){
      sum += ans[i];
     
      if(nt.find(sum) != nt.end())
         t = max(t,nt[sum]);
         
      lst[i] = t;
      nt[sum] = i;
   }
   int q;
   cin >> q;
  
   for(int i = 0;i < q;i ++){
      cin >> l[i] >> r[i];
     ans[i] = 0;
   }
   for(int bit = 18;bit >= 0;bit --){
      for(int i = 0;i <= n;i ++){
         e[i] = lst[i];
      }
      for(int c = 0;c < bit;c ++){
         for(int i = n;i >= 1;i --){
            if (e[i] > -1) e[i] = e[e[i]];
         }
      }
      for(int i = 0;i < q;i ++){
         if(l[i] <= e[r[i]] + 1){
            ans[i] += 1 << bit;
            r[i] = e[r[i]];
         }
      }
   }
   for(int i = 0;i < q;i ++){
      cout << ans[i] << endl;
   }
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 39 / 39