Submission #1173805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173805		therickyzhang	Sum Zero (RMI20_sumzero)	C++20	61 / 100	1094 ms	20676 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

#define tpl_ template
#define tn_ typename
#define f(i, to) for (int i = 0; i < (to); ++i)
#define fe(i, to) for (int i = 1; i <= (to); ++i)
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repr(i, a, b) for (int i = (a); i >= (b); --i)
#define ff first
#define ss second
#define pb push_back
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define setIO(name) ifstream cin(name".in"); ofstream cout(name".out");

// #define int long long
tpl_<tn_ T>        using v = vector<T>;  using ll=long long;  using pii=pair<int,int>;  using pll=pair<ll,ll>;  using iii=tuple<int,int,int>;       using t4=tuple<int,int,int,int>;
using vi=v<int>;   using vb=v<bool>;     using vvb=v<vb>;     using vs=v<string>;       using vvi=v<vi>;        using vll=v<ll>;using vvll=v<vll>; using vpii=v<pii>; using vvpii=v<vpii>; using vpll=v<pll>; using vvpll=v<vpll>;
tpl_<class T, class U> T fstTrue(T l, T r, U ff) { for(++r; l < r;) { T m = l+(r-l) / 2; if(ff(m)) r = m; else l = m+1; } return l; }
tpl_<class T, class U> T lstTrue(T l, T r, U ff) { for(++r; l < r;) { T m = l+(r-l) / 2; if(ff(m)) l = m+1; else r = m; } return l-1; }
tpl_<class T> bool       ckmn(T& a, const T& b) {return b < a ? a = b, 1 : 0;}  tpl_<class T> bool ckmx(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
#define str string
    constexpr int N = 4e5+5; int MOD=1e9+7; constexpr int INF=1e9; ll INFL=0x3f3f3f3f3f3f3f3f; constexpr auto en = "\n"; constexpr auto sp = " ";

constexpr int LG = 8;
int n;
long long prf[N];
int ord[N];
int up[N][LG+1];

void solve(){
    cin>>n;
    prf[0] = 0;
    ord[0] = 0;
    fe(i, n) {
        int x; cin>>x;
        prf[i] = prf[i-1]+x;
        ord[i] = i;
    }
    sort(ord, ord+n+1, [](const int &x, const int &y) {
        return (prf[x] != prf[y] ? prf[x] < prf[y] : x < y);
    });
    
    up[n+1][0] = n+2;
    up[n+2][0] = n+2;
    fe(i, n) up[i][0] = n+2;
    
    rep(i, 0, n) {
        int cur = 0;
        while (i+cur <= n && prf[ord[i]] == prf[ord[i+cur]]) cur++;
        for (int j = i+1; j < i+cur; j++) {
            up[ord[j-1]+1][0] = min(up[ord[j-1]+1][0], ord[j]+1);
        }
        i += cur - 1;
    }
    
    repr(i, n, 1) ckmn(up[i][0], up[i+1][0]);
    fe(i, LG) {
        rep(u, 1, n+2) {
            up[u][i] = up[ up[u][i-1] ][i-1];
        }
    }
    
    int q; cin>>q;
    while(q--) {
        int l, r; cin>>l>>r;
        int res = 0;
        while (up[l][LG] <= r+1) {
            res += (1<<LG);
            l = up[l][LG];
        }
        repr(i, LG, 0) {
            if (up[l][i] <= r+1) {
                res += (1<<i);
                l = up[l][i];
            }
        }
        cout<<res<<en;
    }
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    solve();
    return 0;
}

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