oj.uz

Submission #943497

# Submission time Handle Problem Language Result Execution time Memory
943497 2024-03-11T14:25:27 Z vjudge1 Sum Zero (RMI20_sumzero) C++17
100 / 100
 229 ms 18616 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long

using namespace std;

const int N = 4e5 + 5;
const int mod = 1e9 + 7;

int jump[N], p[N], level[N];
unordered_map<ll, int> f;

void solve(){
    int n;
    cin >> n;
    ll tot = 0;
    int mx = -1;
    level[0] = 1;
    for(int i = 1; i <= n; i++) {
        int a; cin >> a;
        tot += a;
        if(f[tot] || !tot) mx = max(mx, f[tot]);
        f[tot] = i;
        p[i] = mx;
        if(mx == -1) level[i] = 1;
        else
        level[i] = level[p[i]] + 1;
        if(mx >= 0 && level[p[i]] - level[jump[p[i]]] ==  level[jump[p[i]]] - level[jump[jump[p[i]]]]) jump[i] = jump[jump[p[i]]];
        else jump[i] = p[i];
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0; --l;
        while(r) {
            if(p[r] < l) break;
            if(jump[r] >= l) ans += level[r] - level[jump[r]], r = jump[r];
            else ans++, r = p[r];
        }
        cout << ans << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
 }

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 44 ms 6760 KB Output is correct
8 Correct 38 ms 5472 KB Output is correct
9 Correct 53 ms 4408 KB Output is correct
10 Correct 41 ms 6760 KB Output is correct
11 Correct 36 ms 4784 KB Output is correct
12 Correct 46 ms 3920 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 44 ms 6760 KB Output is correct
8 Correct 38 ms 5472 KB Output is correct
9 Correct 53 ms 4408 KB Output is correct
10 Correct 41 ms 6760 KB Output is correct
11 Correct 36 ms 4784 KB Output is correct
12 Correct 46 ms 3920 KB Output is correct
13 Correct 200 ms 14020 KB Output is correct
14 Correct 183 ms 15736 KB Output is correct
15 Correct 213 ms 7812 KB Output is correct
16 Correct 209 ms 16036 KB Output is correct
17 Correct 182 ms 18616 KB Output is correct
18 Correct 229 ms 11924 KB Output is correct