Submission #861294

#	Time	Username	Problem	Language	Result	Execution time	Memory
861294		Palmerin	Sum Zero (RMI20_sumzero)	C++14	61 / 100	501 ms	43848 KiB

sumzero

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

using ll = long long;
using db = long double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;

#define mp make_pair
#define f first
#define s second


typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<bool> vb;

#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ins insert

#define rep(i,b) for(int i=0; i<(b); i++)
#define each(a,x) for(auto& a:x)

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

const char nl = '\n';
const ll MOD = 998244353;

void solve() {
    int n;
    cin >> n;

    ll prefix = 0;
    map<ll,int> prev;
    prev[0] = 0;
    vi next(n+1,-1);
    for(int i=1; i<=n; i++) {
        ll x;
        cin >> x;
        prefix += x;
        if(prev.count(prefix) != 0) {
            next[prev[prefix] + 1] = i;
            if(x == 0) next[i] = i;
        }
        prev[prefix] = i;
    }


    vector<vi> dp(19, vi(n + 1,-1));
    dp[0][n] = next[n];
    for(int i=n-1; i>0; i--) {
        if(dp[0][i+1] != -1 && next[i] != -1) dp[0][i] = min(dp[0][i+1], next[i]);
        else if(next[i] == -1) dp[0][i] = dp[0][i+1];
        else dp[0][i] = next[i];
    }


    for(int i=1; i<19; i++) {
        for(int j=n; j>0; j--) {
            if(dp[i-1][j] != -1 && dp[i-1][j] != n) 
                dp[i][j] = dp[i-1][dp[i-1][j] + 1];
        }
    }

    int q;
    cin >> q;
    while(q--) {
        int l,r;
        cin >> l >> r;
        int ans = 0;
        for(int i=18; i>=0 && l <= r; i--) {
            if(dp[i][l] != -1 && dp[i][l] <= r) {
                l = dp[i][l] + 1;
                ans += (1 << i);
            }
        }
        cout << ans << nl;
    }




}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

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