Submission #846981

#	Time	Username	Problem	Language	Result	Execution time	Memory
846981		TahirAliyev	Sum Zero (RMI20_sumzero)	C++17	100 / 100	368 ms	12044 KiB

sumzero

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 1e9
#define pii pair<int, int>
 
const int MAX = 4e5 + 5, LOGMAX = 3;
 
int n, q;
pii presum[MAX];
int R[MAX];
int par[LOGMAX][MAX];
 
ll lift(int t, int f){
    ll ans = 0;
    for(int j = LOGMAX - 1; j >= 0 && par[0][t] != 0; j--){
        while(par[j][t] <= f && par[j][t] != 0){
            t = par[j][t];
            ans += (1 << (j * 5));
        }
    }
    if(par[0][t] <= f + 1 && par[0][t] != 0) ans++;
    return ans;
}
 
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        int a; scanf("%d", &a);
        presum[i].first = presum[i - 1].first + a;
        presum[i].second = i;
    }
    sort(presum, presum + n + 1);
    for(int l = 0; l < n; l++){
        if(presum[l].first == presum[l + 1].first){
            R[presum[l].second + 1] = presum[l + 1].second;
        }
    }
    scanf("%d", &q);
    int mn = n + 1;
    for(int i = n; i >= 1; i--){
        if(R[i] < mn && R[i] != 0){
            mn = R[i];
        }
        if(mn == n + 1){
            R[i] = 0;
        }
        else{
            R[i] = mn;
        }
    }
    for(int i = 1; i <= n; i++){
        if(!R[i]){
            par[0][i] = 0;
            continue;
        }
        par[0][i] = R[i] + 1;
    }
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            int p = i;
            for(int d = 1; d <= 32; d++){
                p = par[j - 1][p];
            }
            par[j][i] = p;
        }
    }
    while(q--){
        int l, r; scanf("%d%d", &l, &r);
        cout << lift(l, r) << '\n';
    }
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sumzero.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         int a; scanf("%d", &a);
      |                ~~~~~^~~~~~~~~~
sumzero.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
sumzero.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         int l, r; scanf("%d%d", &l, &r);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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