oj.uz

Submission #406008

# Submission time Handle Problem Language Result Execution time Memory
406008 2021-05-17T06:27:17 Z tranxuanbach Sum Zero (RMI20_sumzero) C++17
61 / 100
 719 ms 53208 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;

const int N = 4e5 + 5, M = 19;

int n, q;
int a[N];

ll suf[N]; map <ll, int> mppsuf; int nxt[M][N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("sumzero.inp", "r", stdin);
    // freopen("sumzero.out", "w", stdout);
    cin >> n;
    ForE(i, 1, n){
        cin >> a[i];
    }
    suf[n + 1] = 0;
    mppsuf[0] = n + 1;
    nxt[0][n + 1] = n + 1;
    FordE(i, n, 1){
        suf[i] = suf[i + 1] + a[i];
        nxt[0][i] = nxt[0][i + 1];
        if (mppsuf.count(suf[i])){
            nxt[0][i] = min(nxt[0][i], mppsuf[suf[i]] - 1);
        }
        mppsuf[suf[i]] = i;
    }
    For(j, 1, M){
        ForE(i, 1, n + 1){
            nxt[j][i] = (nxt[j - 1][i] == n + 1 ? n + 1 : nxt[j - 1][nxt[j - 1][i] + 1]);
        }
    }
    cin >> q; while (q--){
        int l, r; cin >> l >> r;
        int ans = 0;
        FordE(j, M - 1, 0){
            if (l <= r and nxt[j][l] <= r){
                ans += (1 << j);
                l = nxt[j][l] + 1;
            }
        }
        cout << ans << endl;
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 4 ms 1100 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 4 ms 1100 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 102 ms 13420 KB Output is correct
8 Correct 106 ms 14124 KB Output is correct
9 Correct 109 ms 11676 KB Output is correct
10 Correct 114 ms 13348 KB Output is correct
11 Correct 96 ms 13348 KB Output is correct
12 Correct 114 ms 11740 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 4 ms 1100 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 102 ms 13420 KB Output is correct
8 Correct 106 ms 14124 KB Output is correct
9 Correct 109 ms 11676 KB Output is correct
10 Correct 114 ms 13348 KB Output is correct
11 Correct 96 ms 13348 KB Output is correct
12 Correct 114 ms 11740 KB Output is correct
13 Runtime error 719 ms 53208 KB Memory limit exceeded
14 Halted 0 ms 0 KB -