oj.uz

Submission #1047129

# Submission time Handle Problem Language Result Execution time Memory
1047129 2024-08-07T09:10:17 Z Circling Index (COCI21_index) C++17
110 / 110
 2299 ms 50892 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int n, q, a, b, minans, maxans, midans;
vector<vector<int>> tree;


void addtotree(int x, int val, int node, int nodel, int noder){
    if (x < nodel || noder <= x) return;
    if (nodel <= x && x < noder) tree[node].push_back(val);
    if (noder - nodel == 1) return;
    addtotree(x, val, 2 * node + 1, nodel, (nodel + noder) / 2);
    addtotree(x, val, 2 * node + 2, (nodel + noder) / 2, noder);
}


int greatercount(int l, int r, int val, int node, int nodel, int noder){
    if (r <= nodel || noder <= l || tree[node][tree[node].size() - 1] < val) return 0;
    if (l <= nodel && noder <= r){
        int mini = 0, maxi = noder - nodel - 1, midi;
        while (mini != maxi){
            midi = (mini + maxi) / 2;
            if (val <= tree[node][midi]) maxi = midi;
            else mini = midi + 1;
        }
        return noder - nodel - mini;
    }
    return greatercount(l, r, val, 2 * node + 1, nodel, (nodel + noder) / 2) + greatercount(l, r, val, 2 * node + 2, (nodel + noder) / 2, noder);
}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> q;
    tree.resize(4 * n);
    for (int i = 0; i < n; i++){
        cin >> a;
        addtotree(i, a, 0, 0, n);
    }
    for (int i = 0; i < 4 * n; i++) sort(tree[i].begin(), tree[i].end());
    while (q--){
        cin >> a >> b;
        minans = 1;
        maxans = n;
        while (minans != maxans){
            midans = (minans + maxans + 1) / 2;
            if (midans <= greatercount(a - 1, b, midans, 0, 0, n)) minans = midans;
            else maxans = midans - 1;
        }
        cout << minans << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 4 ms 660 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 367 ms 12496 KB Output is correct
12 Correct 393 ms 12512 KB Output is correct
13 Correct 382 ms 12496 KB Output is correct
14 Correct 396 ms 12492 KB Output is correct
15 Correct 376 ms 12492 KB Output is correct
16 Correct 373 ms 12424 KB Output is correct
17 Correct 386 ms 12496 KB Output is correct
18 Correct 393 ms 12496 KB Output is correct
19 Correct 368 ms 12536 KB Output is correct
20 Correct 370 ms 12496 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 367 ms 12496 KB Output is correct
12 Correct 393 ms 12512 KB Output is correct
13 Correct 382 ms 12496 KB Output is correct
14 Correct 396 ms 12492 KB Output is correct
15 Correct 376 ms 12492 KB Output is correct
16 Correct 373 ms 12424 KB Output is correct
17 Correct 386 ms 12496 KB Output is correct
18 Correct 393 ms 12496 KB Output is correct
19 Correct 368 ms 12536 KB Output is correct
20 Correct 370 ms 12496 KB Output is correct
21 Correct 2284 ms 50772 KB Output is correct
22 Correct 2268 ms 50696 KB Output is correct
23 Correct 2299 ms 50892 KB Output is correct
24 Correct 2247 ms 50708 KB Output is correct
25 Correct 2231 ms 50684 KB Output is correct
26 Correct 2288 ms 50748 KB Output is correct
27 Correct 2282 ms 50764 KB Output is correct
28 Correct 2248 ms 50748 KB Output is correct
29 Correct 2251 ms 50844 KB Output is correct
30 Correct 2232 ms 50832 KB Output is correct