oj.uz

Submission #964792

# Submission time Handle Problem Language Result Execution time Memory
964792 2024-04-17T14:50:15 Z Pekiban Index (COCI21_index) C++17
110 / 110
 235 ms 22684 KB 
#include <bits/stdc++.h>

using namespace std;

const int mxN = 2e5+2;
int L[mxN], R[mxN], ans[mxN], bit[mxN], c = mxN - 1;
vector<int> d[mxN];
void add(int idx, int x) {
    while (idx < mxN) {
        bit[idx] += x;
        idx |= (idx + 1);
    }
}
int sum(int idx) {
    int s = 0;
    while (idx >= 0) {
        s += bit[idx];
        idx &= (idx + 1);
        --idx;
    }
    return s;
}
int sum(int l, int r) {
    return l ? sum(r) - sum(l-1) : sum(r);
}
void pbs(int l, int r, vector<int> &b) {
    if (r < l || b.empty()) return;
    if (l == r) {
        for (auto u : b) {
            ans[u] = l;
        }
        return;
    }
    int mid = (l + r)/2;
    while (c > mid-1) {
        for (auto u : d[c]) {
            add(u, 1);
        }
        --c;
    }
    while (c < mid-1) {
        ++c;
        for (auto u : d[c]) {
            add(u, -1);
        }
    }
    vector<int> le, ri;
    for (auto x : b) {
        if (sum(L[x], R[x]) >= mid) {
            ri.push_back(x);
        }
        else {
            le.push_back(x);
        }
    }
    b.clear();
    pbs(l, mid, le);
    pbs(mid+1, r, ri);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        d[x].push_back(i);
    }
    vector<int> b;
    for (int i = 0; i < q; ++i) {
        cin >> L[i] >> R[i];
        --L[i], --R[i];
        b.push_back(i);
    }
    pbs(0, n+1, b);
    for (int i = 0; i < q; ++i) {
        cout << ans[i]-1 << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6800 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6800 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6800 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6800 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 50 ms 10588 KB Output is correct
12 Correct 47 ms 10460 KB Output is correct
13 Correct 46 ms 10528 KB Output is correct
14 Correct 49 ms 10544 KB Output is correct
15 Correct 46 ms 10464 KB Output is correct
16 Correct 52 ms 10344 KB Output is correct
17 Correct 56 ms 10516 KB Output is correct
18 Correct 50 ms 10568 KB Output is correct
19 Correct 46 ms 10460 KB Output is correct
20 Correct 54 ms 10364 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6800 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6800 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 50 ms 10588 KB Output is correct
12 Correct 47 ms 10460 KB Output is correct
13 Correct 46 ms 10528 KB Output is correct
14 Correct 49 ms 10544 KB Output is correct
15 Correct 46 ms 10464 KB Output is correct
16 Correct 52 ms 10344 KB Output is correct
17 Correct 56 ms 10516 KB Output is correct
18 Correct 50 ms 10568 KB Output is correct
19 Correct 46 ms 10460 KB Output is correct
20 Correct 54 ms 10364 KB Output is correct
21 Correct 235 ms 22312 KB Output is correct
22 Correct 214 ms 22380 KB Output is correct
23 Correct 234 ms 22392 KB Output is correct
24 Correct 223 ms 22452 KB Output is correct
25 Correct 220 ms 22404 KB Output is correct
26 Correct 226 ms 22356 KB Output is correct
27 Correct 221 ms 22280 KB Output is correct
28 Correct 225 ms 22684 KB Output is correct
29 Correct 218 ms 22260 KB Output is correct
30 Correct 219 ms 22216 KB Output is correct