oj.uz

Submission #519883

# Submission time Handle Problem Language Result Execution time Memory
519883 2022-01-27T14:03:42 Z Vianti Index (COCI21_index) C++17
60 / 110
 2500 ms 142888 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll mod = 1e9 + 7;

struct Node {
    Node* l, * r;
    int sum;

    Node(Node* left, Node* right, int v) {
        l = left;
        r = right;
        sum = v;
    }

    Node() {
        l = nullptr;
        r = nullptr;
        sum = 0;
    }
};

struct SegTree {
    int sz = 0;

    Node* createTree(int l, int r) {
        if (l == r) {
            Node* res = new Node(nullptr, nullptr, 0);
            return res;
        }
        int m = (l + r) >> 1;
        Node* nd1 = createTree(l, m);
        Node* nd2 = createTree(m + 1, r);
        Node* res = new Node(nd1, nd2, 0);
        return res;
    }

    Node* build(int n) {
        sz = 1;
        while (sz < n)sz <<= 1;
        return createTree(0, sz - 1);
    }

    Node* add(Node* v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            Node* nd = new Node(nullptr, nullptr, val + v->sum);
            return nd;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm) {
            Node* nd = add(v->l, tl, tm, pos, val);
            Node* res = new Node(nd, v->r, nd->sum + v->r->sum);
            return res;
        } else {
            Node* nd = add(v->r, tm + 1, tr, pos, val);
            Node* res = new Node(v->l, nd, v->l->sum + nd->sum);
            return res;
        }
    }

    Node* add(Node* root, int pos, int val) {
        return add(root, 0, sz - 1, pos, val);
    }

    int getSum(Node* v, int tl, int tr, int l, int r) const {
        if (tl > tr)return 0;
        if (tl > r || tr < l)return 0;
        if (tl >= l && tr <= r)return v->sum;
        int tm = (tl + tr) >> 1;
        return getSum(v->l, tl, tm, l, r) + getSum(v->r, tm + 1, tr, l, r);
    }

    int getSum(Node* root, int l, int r) const {
        return getSum(root, 0, sz - 1, l, r);
    }
};

const int maxP = 200000;

int query(int x, int l, int r, const vector<Node*>& roots, const SegTree& tree) {
    if (l == 0)return tree.getSum(roots[r], x, maxP - 1);
    else return tree.getSum(roots[r], x, maxP - 1) - tree.getSum(roots[l - 1], x, maxP - 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    SegTree tree;
    Node* root = tree.build(maxP);
    vector<Node*> roots(n);
    roots[0] = tree.add(root, a[0] - 1, 1);
    for (int i = 1; i < n; i++) {
        roots[i] = tree.add(roots[i - 1], a[i] - 1, 1);
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int left = 1;
        int right = r - l + 2;
        while (right - left > 1) {
            int x = (right + left) >> 1;
            if (query(x - 1, l, r, roots, tree) >= x) {
                left = x;
            } else {
                right = x;
            }
        }
        cout << left << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17228 KB Output is correct
2 Correct 21 ms 17236 KB Output is correct
3 Correct 26 ms 17276 KB Output is correct
4 Correct 21 ms 17344 KB Output is correct
5 Correct 22 ms 17344 KB Output is correct
6 Correct 23 ms 17244 KB Output is correct
7 Correct 29 ms 17308 KB Output is correct
8 Correct 28 ms 17308 KB Output is correct
9 Correct 22 ms 17232 KB Output is correct
10 Correct 22 ms 17220 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17228 KB Output is correct
2 Correct 21 ms 17236 KB Output is correct
3 Correct 26 ms 17276 KB Output is correct
4 Correct 21 ms 17344 KB Output is correct
5 Correct 22 ms 17344 KB Output is correct
6 Correct 23 ms 17244 KB Output is correct
7 Correct 29 ms 17308 KB Output is correct
8 Correct 28 ms 17308 KB Output is correct
9 Correct 22 ms 17232 KB Output is correct
10 Correct 22 ms 17220 KB Output is correct
11 Correct 408 ms 48300 KB Output is correct
12 Correct 457 ms 48172 KB Output is correct
13 Correct 452 ms 48152 KB Output is correct
14 Correct 409 ms 48120 KB Output is correct
15 Correct 440 ms 48176 KB Output is correct
16 Correct 423 ms 48240 KB Output is correct
17 Correct 432 ms 48068 KB Output is correct
18 Correct 472 ms 48212 KB Output is correct
19 Correct 410 ms 48264 KB Output is correct
20 Correct 435 ms 48220 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17228 KB Output is correct
2 Correct 21 ms 17236 KB Output is correct
3 Correct 26 ms 17276 KB Output is correct
4 Correct 21 ms 17344 KB Output is correct
5 Correct 22 ms 17344 KB Output is correct
6 Correct 23 ms 17244 KB Output is correct
7 Correct 29 ms 17308 KB Output is correct
8 Correct 28 ms 17308 KB Output is correct
9 Correct 22 ms 17232 KB Output is correct
10 Correct 22 ms 17220 KB Output is correct
11 Correct 408 ms 48300 KB Output is correct
12 Correct 457 ms 48172 KB Output is correct
13 Correct 452 ms 48152 KB Output is correct
14 Correct 409 ms 48120 KB Output is correct
15 Correct 440 ms 48176 KB Output is correct
16 Correct 423 ms 48240 KB Output is correct
17 Correct 432 ms 48068 KB Output is correct
18 Correct 472 ms 48212 KB Output is correct
19 Correct 410 ms 48264 KB Output is correct
20 Correct 435 ms 48220 KB Output is correct
21 Execution timed out 2561 ms 142888 KB Time limit exceeded
22 Halted 0 ms 0 KB -