oj.uz

Submission #516994

# Submission time Handle Problem Language Result Execution time Memory
516994 2022-01-22T10:44:02 Z Stickfish Sum Zero (RMI20_sumzero) C++17
61 / 100
 311 ms 15896 KB 
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ll = long long;

const int MAXN = 100000;
int a[MAXN];
vector<int> redg[MAXN];

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    map<ll, int> mp;
    mp[0] = -1;
    ll psm = 0;
    for (int i = 0; i < n; ++i) {
        psm += a[i];
        if (mp.find(psm) == mp.end()) {
            a[i] = -2;
        } else {
            a[i] = mp[psm];
        }
        if (i && a[i - 1] > a[i])
            a[i] = a[i - 1];
        if (a[i] >= -1) {
            redg[i].push_back(a[i]);
            for (int j = 1;; ++j) {
                int v = redg[i][j - 1];
                if (v == -1 || j - 1 >= redg[v].size())
                    break;
                redg[i].push_back(redg[v][j - 1]);
            }
        }
        mp[psm] = i;
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int v = r - 1;
        int ans = 0;
        int j = 20;
        while (true) {
            if (v < l || j == -1)
                break;
            if (j >= redg[v].size() || redg[v][j] + 1 < l) {
                --j;
            } else {
                ans += (1 << j);
                v = redg[v][j];
            }
        }
        cout << ans << endl;
    }
}

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:32:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                 if (v == -1 || j - 1 >= redg[v].size())
      |                                ~~~~~~^~~~~~~~~~~~~~~~~
sumzero.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (j >= redg[v].size() || redg[v][j] + 1 < l) {
      |                 ~~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3148 KB Output is correct
2 Correct 13 ms 3068 KB Output is correct
3 Correct 13 ms 3204 KB Output is correct
4 Correct 13 ms 3140 KB Output is correct
5 Correct 16 ms 2936 KB Output is correct
6 Correct 14 ms 3148 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3148 KB Output is correct
2 Correct 13 ms 3068 KB Output is correct
3 Correct 13 ms 3204 KB Output is correct
4 Correct 13 ms 3140 KB Output is correct
5 Correct 16 ms 2936 KB Output is correct
6 Correct 14 ms 3148 KB Output is correct
7 Correct 285 ms 14368 KB Output is correct
8 Correct 283 ms 15896 KB Output is correct
9 Correct 311 ms 13464 KB Output is correct
10 Correct 290 ms 15188 KB Output is correct
11 Correct 298 ms 15144 KB Output is correct
12 Correct 295 ms 13484 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3148 KB Output is correct
2 Correct 13 ms 3068 KB Output is correct
3 Correct 13 ms 3204 KB Output is correct
4 Correct 13 ms 3140 KB Output is correct
5 Correct 16 ms 2936 KB Output is correct
6 Correct 14 ms 3148 KB Output is correct
7 Correct 285 ms 14368 KB Output is correct
8 Correct 283 ms 15896 KB Output is correct
9 Correct 311 ms 13464 KB Output is correct
10 Correct 290 ms 15188 KB Output is correct
11 Correct 298 ms 15144 KB Output is correct
12 Correct 295 ms 13484 KB Output is correct
13 Runtime error 19 ms 6348 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -