Submission #517005

# Submission time Handle Problem Language Result Execution time Memory
517005 2022-01-22T11:03:41 Z Stickfish Sum Zero (RMI20_sumzero) C++17
61 / 100
982 ms 45152 KB
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ll = long long;
#define endl '\n'

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:38:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                     if (v == -1 || j - 1 >= redg[v].size()) {
      |                                    ~~~~~~^~~~~~~~~~~~~~~~~
sumzero.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             if (j >= redg[v].size() || redg[v][j] + 1 < l) {
      |                 ~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 10 ms 10188 KB Output is correct
2 Correct 8 ms 10052 KB Output is correct
3 Correct 11 ms 10060 KB Output is correct
4 Correct 8 ms 9992 KB Output is correct
5 Correct 8 ms 10036 KB Output is correct
6 Correct 9 ms 10060 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 10188 KB Output is correct
2 Correct 8 ms 10052 KB Output is correct
3 Correct 11 ms 10060 KB Output is correct
4 Correct 8 ms 9992 KB Output is correct
5 Correct 8 ms 10036 KB Output is correct
6 Correct 9 ms 10060 KB Output is correct
7 Correct 125 ms 17748 KB Output is correct
8 Correct 127 ms 18172 KB Output is correct
9 Correct 125 ms 15984 KB Output is correct
10 Correct 125 ms 17668 KB Output is correct
11 Correct 108 ms 17476 KB Output is correct
12 Correct 139 ms 15820 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 10188 KB Output is correct
2 Correct 8 ms 10052 KB Output is correct
3 Correct 11 ms 10060 KB Output is correct
4 Correct 8 ms 9992 KB Output is correct
5 Correct 8 ms 10036 KB Output is correct
6 Correct 9 ms 10060 KB Output is correct
7 Correct 125 ms 17748 KB Output is correct
8 Correct 127 ms 18172 KB Output is correct
9 Correct 125 ms 15984 KB Output is correct
10 Correct 125 ms 17668 KB Output is correct
11 Correct 108 ms 17476 KB Output is correct
12 Correct 139 ms 15820 KB Output is correct
13 Runtime error 982 ms 45152 KB Memory limit exceeded
14 Halted 0 ms 0 KB -