Submission #846973

#	Time	Username	Problem	Language	Result	Execution time	Memory
846973		TahirAliyev	Sum Zero (RMI20_sumzero)	C++17	61 / 100	400 ms	35152 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 = 5; 
 
int n, q;
int arr[MAX];
int presum[MAX];
int R[MAX];
int E[MAX];
int par[LOGMAX][MAX];
set<pii> s;
 
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 * 3));
        }
    }
    if(par[0][t] <= f + 1 && par[0][t] != 0) ans++;
    return ans;
}
 
int main(){
    scanf("%d", &n);
    s.insert({0, 0});
    for(int i = 1; i <= n; i++){
        scanf("%d", &arr[i]);
        presum[i] = presum[i - 1] + arr[i];
        s.insert({presum[i], i});
    }
    for(int l = 0; l < n; l++){
        s.erase(s.find({presum[l], l}));
        auto itr = s.lower_bound({presum[l], 0});
        if(itr == s.end() || (*itr).first != presum[l]) continue;
        R[l + 1] = (*itr).second;
    }
    scanf("%d", &q);
    s.clear();
    for(int i = 1; i <= n; i++){
        if(R[i]) s.insert({R[i], i});
    }
    for(int i = 1; i <= n; i++){
        if(R[i - 1] && i){
            s.erase(s.find({R[i - 1], i - 1}));
        }
        E[i] = (*s.begin()).first;
    }
    for(int i = 1; i <= n; i++){
        if(!E[i]){
            par[0][i] = 0;
            continue;
        }
        par[0][i] = E[i] + 1;
    }
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            par[j][i] = par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][par[j - 1][i]]]]]]]];
        }
    }
    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:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sumzero.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
sumzero.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
sumzero.cpp:70:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         int l, r; scanf("%d%d", &l, &r);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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