Submission #1118637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118637		pera	Sum Zero (RMI20_sumzero)	C++17	61 / 100	258 ms	26304 KiB

sumzero

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 4e5 + 1;
int lst[N] , e[N];
struct qu{
   int l , r , ans = 0;
} s[N];
unordered_map<LL , int> nt;
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n;
   cin >> n;
   LL sum = 0;
   nt[0] = 0;
   lst[0] = -1;
   for(int i = 1;i <= n;i ++){
      int x;
      cin >> x;
      sum += x;
      if(nt.find(sum) != nt.end()){
         lst[i] = nt[sum];
      }else{
         lst[i] = -1;
      }
      lst[i] = max(lst[i] , lst[i - 1]);
      nt[sum] = i;
   }
   int q;
   cin >> q;
   for(int i = 0;i < q;i ++){
      cin >> s[i].l >> s[i].r;
   }
   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 >= 0;i --){
            e[i] = (e[i] > -1 ? e[e[i]] : -1);
         }
      }
      for(int i = 0;i < q;i ++){
         if(e[s[i].r] >= s[i].l - 1){
            s[i].ans += 1 << bit;
            s[i].r = e[s[i].r];
         }
      }
   }
   for(int i = 0;i < q;i ++){
      cout << s[i].ans << '\n';
   }
}

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