oj.uz

Submission #517001

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

const int MAXN = 400000;
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 = i;
                for (int t = 0; t < 4; ++t) {
                    //cout << i << ' ' << j << ' ' << v << endl;
                    if (v == -1 || j - 1 >= redg[v].size()) {
                        v = -2;
                        break;
                    } else {
                        v = redg[v][j - 1];
                    }
                }
                if (v != -2)
                    redg[i].push_back(v);
                else
                    break;
            }
        }
        mp[psm] = i;
    }
    //return 0;
    mp.clear();
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int v = r - 1;
        int ans = 0;
        int j = 10;
        while (true) {
            if (v < l || j == -1)
                break;
            if (j >= redg[v].size() || redg[v][j] + 1 < l) {
                --j;
            } else {
                ans += (1 << j) << j;
                v = redg[v][j];
            }
        }
        cout << ans << endl;
    }
}

Compilation message

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10060 KB Output is correct
2 Correct 16 ms 9932 KB Output is correct
3 Correct 18 ms 10056 KB Output is correct
4 Correct 16 ms 10072 KB Output is correct
5 Correct 17 ms 10016 KB Output is correct
6 Correct 21 ms 10112 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10060 KB Output is correct
2 Correct 16 ms 9932 KB Output is correct
3 Correct 18 ms 10056 KB Output is correct
4 Correct 16 ms 10072 KB Output is correct
5 Correct 17 ms 10016 KB Output is correct
6 Correct 21 ms 10112 KB Output is correct
7 Correct 302 ms 17744 KB Output is correct
8 Correct 318 ms 18308 KB Output is correct
9 Correct 302 ms 15816 KB Output is correct
10 Correct 328 ms 17684 KB Output is correct
11 Correct 300 ms 17520 KB Output is correct
12 Correct 341 ms 15844 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10060 KB Output is correct
2 Correct 16 ms 9932 KB Output is correct
3 Correct 18 ms 10056 KB Output is correct
4 Correct 16 ms 10072 KB Output is correct
5 Correct 17 ms 10016 KB Output is correct
6 Correct 21 ms 10112 KB Output is correct
7 Correct 302 ms 17744 KB Output is correct
8 Correct 318 ms 18308 KB Output is correct
9 Correct 302 ms 15816 KB Output is correct
10 Correct 328 ms 17684 KB Output is correct
11 Correct 300 ms 17520 KB Output is correct
12 Correct 341 ms 15844 KB Output is correct
13 Execution timed out 1010 ms 46124 KB Time limit exceeded
14 Halted 0 ms 0 KB -