oj.uz

Submission #942764

# Submission time Handle Problem Language Result Execution time Memory
942764 2024-03-11T04:12:30 Z Pannda Sum Zero (RMI20_sumzero) C++17
100 / 100
 239 ms 19004 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU {
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> nxt = [&] {
        vector<pair<long long, int>> a(n + 1);
        a[0] = {0, 0};
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            a[i + 1] = { a[i].first + x, i + 1 };
        }
        sort(a.begin(), a.end());
        vector<pair<int, int>> intervals;
        for (int i = 0; i < n; i++) {
            if (a[i].first == a[i + 1].first) {
                intervals.push_back({a[i].second, a[i + 1].second});
            }
        }
        a.clear();
        vector<pair<long long, int>>().swap(a);
        sort(intervals.begin(), intervals.end(), [&](pair<int, int> x, pair<int, int> y) {
            return x.second < y.second;
        });
        vector<int> nxt(n + 1, n + 1);
        int last_l = -1, last_r = -1;
        for (int i = 0; i < intervals.size(); i++) {
            auto [l, r] = intervals[i];
            if (l <= last_l) continue;
            nxt[l] = r;
            last_l = l;
            last_r = r;
        }
        for (int i = n - 1; i >= 0; i--) {
            if (nxt[i] == n + 1) nxt[i] = nxt[i + 1];
        }
        intervals.clear();
        vector<pair<int, int>>().swap(intervals);
        return nxt;
    }();

    int q;
    cin >> q;
    vector<array<int, 3>> queries(q);
    vector<int> ans(q, -1);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        queries[i] = {r, l, i};
    }
    sort(queries.begin(), queries.end());

    vector<int> f(n + 1, 0);
    auto fix = [&](auto self, int i, int r) -> void {
        if (nxt[i] > r) return;
        f[i] = max(f[i], 1);
        self(self, nxt[i], r);
        f[i] += f[nxt[i]];
        if (nxt[nxt[i]] <= r) nxt[i] = nxt[nxt[i]];
    };

    auto get = [&](int i, int r) {
        fix(fix, i, r);
        return f[i];
    };

    for (auto [r, l, i] : queries) {
        ans[i] = get(l, r);
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}

Compilation message

sumzero.cpp: In lambda function:
sumzero.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < intervals.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
sumzero.cpp:35:26: warning: variable 'last_r' set but not used [-Wunused-but-set-variable]
   35 |         int last_l = -1, last_r = -1;
      |                          ^~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 43 ms 3188 KB Output is correct
8 Correct 44 ms 3124 KB Output is correct
9 Correct 50 ms 3044 KB Output is correct
10 Correct 42 ms 3032 KB Output is correct
11 Correct 44 ms 2916 KB Output is correct
12 Correct 59 ms 3048 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 43 ms 3188 KB Output is correct
8 Correct 44 ms 3124 KB Output is correct
9 Correct 50 ms 3044 KB Output is correct
10 Correct 42 ms 3032 KB Output is correct
11 Correct 44 ms 2916 KB Output is correct
12 Correct 59 ms 3048 KB Output is correct
13 Correct 179 ms 11792 KB Output is correct
14 Correct 184 ms 11536 KB Output is correct
15 Correct 219 ms 19004 KB Output is correct
16 Correct 181 ms 18044 KB Output is correct
17 Correct 189 ms 18896 KB Output is correct
18 Correct 239 ms 18796 KB Output is correct