oj.uz

Submission #538745

# Submission time Handle Problem Language Result Execution time Memory
538745 2022-03-17T16:29:15 Z Jomnoi Index (COCI21_index) C++17
60 / 110
 2500 ms 152096 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 2e5 + 10;

int p[N];
vector <int> idx_paper[N];

class Node {
public :
    int sum;
    Node *l, *r;
    Node(int s) : sum(s), l(NULL), r(NULL) {}
    Node(Node *L, Node *R) : sum(0), l(L), r(R) {
        if(L != NULL) {
            sum += L->sum;
        }
        if(R != NULL) {
            sum += R->sum;
        }
    }
    Node(Node *copy) : sum(copy->sum), l(copy->l), r(copy->r) {}
};
Node *root[N];

Node *build(int l, int r) {
    if(l == r) {
        return new Node(0);
    }

    int mid = (l + r) / 2;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node *update(Node *node, int l, int r, int q) {
    if(l == r) {
        return new Node(1);
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        return new Node(update(node->l, l, mid, q), node->r);
    }
    return new Node(node->l, update(node->r, mid + 1, r, q));
}

int query(Node *node, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return 0;
    }
    if(ql <= l and r <= qr) {
        return node->sum;
    }

    int mid = (l + r) / 2;
    return query(node->l, l, mid, ql, qr) + query(node->r, mid + 1, r, ql, qr);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        idx_paper[p[i]].push_back(i);
    }

    root[n + 1] = build(1, n);
    for(int i = n; i >= 1; i--) {
        root[i] = new Node(root[i + 1]);
        for(auto idx : idx_paper[i]) {
            root[i] = update(root[i], 1, n, idx);
        }
    }

    while(q--) {
        int a, b;
        cin >> a >> b;

        int range = b - a + 1;
        int l = 1, r = range, pos = 1;
        while(l <= r) {
            int mid = (l + r) / 2;

            if(query(root[mid], 1, n, a, b) < mid) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
                pos = mid;
            }
        }
        cout << pos << '\n';
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5460 KB Output is correct
2 Correct 6 ms 5400 KB Output is correct
3 Correct 6 ms 5416 KB Output is correct
4 Correct 6 ms 5420 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5588 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 5 ms 5424 KB Output is correct
10 Correct 5 ms 5460 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5460 KB Output is correct
2 Correct 6 ms 5400 KB Output is correct
3 Correct 6 ms 5416 KB Output is correct
4 Correct 6 ms 5420 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5588 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 5 ms 5424 KB Output is correct
10 Correct 5 ms 5460 KB Output is correct
11 Correct 380 ms 38580 KB Output is correct
12 Correct 311 ms 38660 KB Output is correct
13 Correct 348 ms 38436 KB Output is correct
14 Correct 306 ms 38604 KB Output is correct
15 Correct 299 ms 38572 KB Output is correct
16 Correct 379 ms 38448 KB Output is correct
17 Correct 295 ms 38472 KB Output is correct
18 Correct 356 ms 38484 KB Output is correct
19 Correct 318 ms 38496 KB Output is correct
20 Correct 355 ms 38592 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5460 KB Output is correct
2 Correct 6 ms 5400 KB Output is correct
3 Correct 6 ms 5416 KB Output is correct
4 Correct 6 ms 5420 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5588 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 5 ms 5424 KB Output is correct
10 Correct 5 ms 5460 KB Output is correct
11 Correct 380 ms 38580 KB Output is correct
12 Correct 311 ms 38660 KB Output is correct
13 Correct 348 ms 38436 KB Output is correct
14 Correct 306 ms 38604 KB Output is correct
15 Correct 299 ms 38572 KB Output is correct
16 Correct 379 ms 38448 KB Output is correct
17 Correct 295 ms 38472 KB Output is correct
18 Correct 356 ms 38484 KB Output is correct
19 Correct 318 ms 38496 KB Output is correct
20 Correct 355 ms 38592 KB Output is correct
21 Execution timed out 2577 ms 152096 KB Time limit exceeded
22 Halted 0 ms 0 KB -