oj.uz

Submission #517004

# Submission time Handle Problem Language Result Execution time Memory
517004 2022-01-22T11:02:54 Z Stickfish Sum Zero (RMI20_sumzero) C++17
61 / 100
 1000 ms 44040 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() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    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:37:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                     if (v == -1 || j - 1 >= redg[v].size()) {
      |                                    ~~~~~~^~~~~~~~~~~~~~~~~
sumzero.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (j >= redg[v].size() || redg[v][j] + 1 < l) {
      |                 ~~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10060 KB Output is correct
2 Correct 13 ms 10060 KB Output is correct
3 Correct 13 ms 10060 KB Output is correct
4 Correct 14 ms 10060 KB Output is correct
5 Correct 13 ms 9932 KB Output is correct
6 Correct 14 ms 10060 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10060 KB Output is correct
2 Correct 13 ms 10060 KB Output is correct
3 Correct 13 ms 10060 KB Output is correct
4 Correct 14 ms 10060 KB Output is correct
5 Correct 13 ms 9932 KB Output is correct
6 Correct 14 ms 10060 KB Output is correct
7 Correct 269 ms 17708 KB Output is correct
8 Correct 240 ms 18168 KB Output is correct
9 Correct 270 ms 15840 KB Output is correct
10 Correct 273 ms 17768 KB Output is correct
11 Correct 226 ms 17372 KB Output is correct
12 Correct 232 ms 15936 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10060 KB Output is correct
2 Correct 13 ms 10060 KB Output is correct
3 Correct 13 ms 10060 KB Output is correct
4 Correct 14 ms 10060 KB Output is correct
5 Correct 13 ms 9932 KB Output is correct
6 Correct 14 ms 10060 KB Output is correct
7 Correct 269 ms 17708 KB Output is correct
8 Correct 240 ms 18168 KB Output is correct
9 Correct 270 ms 15840 KB Output is correct
10 Correct 273 ms 17768 KB Output is correct
11 Correct 226 ms 17372 KB Output is correct
12 Correct 232 ms 15936 KB Output is correct
13 Execution timed out 1073 ms 44040 KB Time limit exceeded
14 Halted 0 ms 0 KB -