제출 #1118623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118623		pera	Sum Zero (RMI20_sumzero)	C++17	61 / 100	412 ms	47848 KiB

sumzero

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n;
   cin >> n;
   LL a[n + 1];
   for(int i = 1;i <= n;i ++){
      cin >> a[i];
   }
   const int LOG = 19;
   int up[n + 1][LOG];
   up[0][0] = -1;
   vector<int> lst(n + 1); 
   vector<LL> pre(n + 1);
   for(int i = 1;i <= n;i ++){
      pre[i] = pre[i - 1] + a[i];
   }
   vector<int> o(n + 1);
   iota(o.begin() , o.end() , 0);
   sort(o.begin() , o.end() , [&](int i , int j){
      return pair<int , int>{pre[i] , i} < pair<int , int>{pre[j] , j};
   });
   for(int i = 0;i <= n;i ++){
      int j = i;
      while(j <= n && pre[o[i]] == pre[o[j]]){
         lst[o[j]] = (j > i ? o[j - 1] : -1);
         ++j;
      }
      i = j - 1;
   }
   for(int i = 1;i <= n;i ++){
      up[i][0] = max(up[i - 1][0] , lst[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';
   }
}
/*
10
1 2 -3 0 1 -4 3 2 -1 1 3
1 10
1 5
2 9
*/

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