oj.uz

Submission #770453

# Submission time Handle Problem Language Result Execution time Memory
770453 2023-07-01T08:51:00 Z dxz05 Sum Zero (RMI20_sumzero) C++17
100 / 100
 590 ms 19028 KB 
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 4e5 + 2;

const int K = 64; // base
const int L = 4;  // K^L >= N

int a[N];
int go[N][L];

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

    for (int i = 1; i <= n; i++) cin >> a[i];

    unordered_map<ll, int> mp;
    mp[0] = n + 1;

    ll sum = 0;
    for (int i = n; i >= 1; i--){
        sum += a[i];
        if (mp.find(sum) != mp.end()){
            a[i] = mp[sum];
        } else {
            a[i] = -1;
        }
        mp[sum] = i;
    }

    int where = -1;
    for (int i = n; i >= 1; i--){
        if (a[i] != -1){
            if (where == -1){
                where = a[i];
            } else {
                where = min(where, a[i]);
            }
        }
        go[i][0] = where;
    }
    go[n + 1][0] = -1;

    for (int j = 1; j < L; j++){
        for (int i = 1; i <= n + 1; i++){
            int v = i;
            for (int t = 0; t < K && v != -1; t++){
                v = go[v][j - 1];
            }

            go[i][j] = v;
        }
    }

    vector<int> pw(L);
    pw[0] = 1;
    for (int i = 1; i < L; i++) pw[i] = pw[i - 1] * K;

    int q;
    cin >> q;

    while (q--){
        int l, r;
        cin >> l >> r;
        ++r;

        int ans = 0;
        int v = l;
        for (int i = L - 1; i >= 0; i--){
            while (go[v][i] != -1 && go[v][i] <= r){
                v = go[v][i];
                ans += pw[i];
            }
        }

        cout << ans << "\n";
    }

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
    //cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        //cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:98:13: warning: unused variable 'startTime' [-Wunused-variable]
   98 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 101 ms 4300 KB Output is correct
8 Correct 65 ms 4908 KB Output is correct
9 Correct 110 ms 3304 KB Output is correct
10 Correct 107 ms 4276 KB Output is correct
11 Correct 68 ms 4060 KB Output is correct
12 Correct 103 ms 3264 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 101 ms 4300 KB Output is correct
8 Correct 65 ms 4908 KB Output is correct
9 Correct 110 ms 3304 KB Output is correct
10 Correct 107 ms 4276 KB Output is correct
11 Correct 68 ms 4060 KB Output is correct
12 Correct 103 ms 3264 KB Output is correct
13 Correct 499 ms 16576 KB Output is correct
14 Correct 362 ms 18860 KB Output is correct
15 Correct 549 ms 10880 KB Output is correct
16 Correct 548 ms 19028 KB Output is correct
17 Correct 385 ms 15864 KB Output is correct
18 Correct 590 ms 17916 KB Output is correct