Submission #1118621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118621		pera	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1051 ms	65536 KiB

sumzero

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
   int n;
   cin >> n;
   vector<LL> a(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> a[i];
   }
   map<LL , int> lst;
   LL s = 0;
   lst[s] = 0;
   const int LOG = 20;
   vector<vector<int>> up(n + 1 , vector<int>(LOG));
   up[0][0] = -1;
   for(int i = 1;i <= n;i ++){
      s += a[i];
      if(lst.find(s) != lst.end()){
         up[i][0] = lst[s];
      }else{
        up[i][0] = -1;
      }
      up[i][0] = max(up[i][0] , up[i - 1][0]);
      lst[s] = i;
   }
   for(int bit = 1;bit < LOG;bit ++){
      for(int i = 0;i <= n;i ++){
         up[i][bit] = (up[i][bit - 1] >= 0 ? up[up[i][bit - 1]][bit - 1] : -1);
      }
   }
   int q;
   cin >> q;
   while(q--){
      int l , r;
      cin >> l >> r;
      int c = 0;
      for(int bit = LOG - 1;bit >= 0;bit --){
         if(up[r][bit] >= l - 1){
            c += 1 << bit;
            r = up[r][bit];
         }
      }
      cout << c << '\n';
   }
}

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