Submission #1140743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140743		azaylibelz	Sum Zero (RMI20_sumzero)	C++20	100 / 100	510 ms	14148 KiB

sumzero

#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iterator>
#include <stack>
#include <queue>
#include <set>

using namespace std;
typedef int ll;
typedef long double ld;
const ll MOD = 1e9 + 7;
const ll lg = 4, maxn = 4e5 + 1, Base = 32;
int sparseTable[maxn][lg], power[lg];

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    power[0] = 1;
    for (int i = 1; i < lg; i++) power[i] = Base * power[i - 1];
    ll n; cin >> n;
    vector<ll> arr(n);
    for(ll i = 0; i < n; i++) cin >> arr[i];
    for(ll i = 0; i <= n + 1; i++) {
        for(ll j = 0; j < lg; j++) {
            sparseTable[i][j] = n + 1;
        }
    }
    long long sm = 0;
    vector<long long> pSum;
    pSum.push_back(0);
    for(ll i = n - 1; i >= 0; i--) {
        sm += arr[i];
        pSum.push_back(sm);
    }
    sort(pSum.begin(), pSum.end());
    pSum.resize(unique(pSum.begin(), pSum.end()) - pSum.begin());
    sm = 0;
    vector<ll> go(pSum.size(), n + 1);
    go[lower_bound(pSum.begin(), pSum.end(), sm) - pSum.begin()] = n;
    for(ll i = n - 1; i >= 0; i--) {
        sm += arr[i];
        sparseTable[i][0] = go[lower_bound(pSum.begin(), pSum.end(), sm) - pSum.begin()];
        go[lower_bound(pSum.begin(), pSum.end(), sm) - pSum.begin()] = i;
    }
    for(ll i = n - 2; i >= 0; i--) {
        sparseTable[i][0] = min(sparseTable[i][0], sparseTable[i + 1][0]);
    }
    for (ll j = 1; j < lg; j++) {
        for (ll i = 0; i < n; i++) {
            ll x = i;
            for(ll k = 0; k < Base; k++) 
                x = sparseTable[x][j - 1];
            sparseTable[i][j] = x;
        }
    }
    ll q; cin >> q;
    for(ll i = 0; i < q; i++) {
        ll l, r, res = 0; cin >> l >> r; l--;
        ll x = lg - 1;
        while(x >= 0) {
            if(sparseTable[l][x] <= r) {
                res += power[x];
                l = sparseTable[l][x];
            }
            else {
                x--;
            }
        }
        cout << res << "\n";
    }
    return 0;
}

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