제출 #1182921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182921		al95ireyiz	Sum Zero (RMI20_sumzero)	C++20	61 / 100	72 ms	20296 KiB

sumzero

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;
const ll INF = 1e9;
const ll INFL = 1e18;
ll n,m,k=0;
ll a[maxn];
const ll lg = 20;
ll up[maxn][lg];
#define d(x) cout<<"DEBUG: "<<(#x)<<" = "<<x<<'\n'
void _(){
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>a[i];
    ll cm = accumulate(a+1, a+n+1, 0ll);
    map<ll, ll>bf;
    ll tmp = n+1;
    for(ll i=n;i>=0;i--){
        if(bf.count(cm)) tmp = min(tmp, bf[cm]);
        bf[cm] = i;
        up[i][0] = tmp;
        cm -= a[i];
    }
    up[n+1][0] = n+1;
    for(ll i=1;i<lg;i++){
        for(ll j=0;j<=n+1;j++){
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
    cin>>m;
    for(ll t=1;t<=m;t++){
        ll l, r;
        cin>>l>>r;
        ll cv = 0;
        l --;
        for(ll i=lg-1;i>=0;i--){
            if(up[l][i] == 0) continue;
            if(up[l][i] <= r){
                cv += 1ll<<i;
                l = up[l][i];
            }
        }
        cout<<cv<<'\n';
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    ll t=1;
    // cin>>t;
    while(t--){
        _();
    }
}

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