oj.uz

Submission #476211

# Submission time Handle Problem Language Result Execution time Memory
476211 2021-09-25T10:48:42 Z Shin Index (COCI21_index) C++14
110 / 110
 579 ms 136368 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct Node {
    int val;
    Node *l = NULL, *r = NULL;

    Node(int _val = 0) : val(_val) {};
    Node(Node *ll, Node *rr) : l(ll), r(rr) {
        val = (l ? l->val : 0) + (r ? r->val : 0);
    }
};

struct P_IT {
    vector<Node*> root;
    int n;

    P_IT(int _n = 0) : n(_n) {
        root.push_back(build(1, n));
    }
    
    Node* build(int l, int r) {
        if (l == r) return new Node();
        int mid = (l + r) >> 1;
        return new Node(build(l, mid), build(mid + 1, r));
    }

    Node* update(Node* node, int pos, int val, int l, int r) {
        if (l == r) return new Node(node->val + val);
        int mid = (l + r) >> 1;
        if (mid < pos) return new Node(node->l, update(node->r, pos, val, mid + 1, r));
        return new Node (update(node->l, pos, val, l, mid), node->r);
    }

    int get(Node* ll, Node* rr, int sum, int l, int r) {
        if (l == r) return l;
        int mid = (l + r) >> 1, delta = rr->r->val - ll->r->val;
        if (mid >= delta + sum) return get(ll->l, rr->l, sum + delta, l, mid);
        return get(ll->r, rr->r, sum, mid + 1, r);
    }

    void update(int pos, int val) {
        root.push_back(update(root.back(), pos, val, 1, n));
    }

    int query(int l, int r) {
        return get(root[l - 1], root[r], 0, 1, n);
    }
};

void solve(void) { 
    int n, q; cin >> n >> q;
    P_IT st(N);
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        st.update(x, 1);
    }

    while (q --) {
        int l, r; cin >> l >> r;
        cout << st.query(l, r) << '\n';
    }
} 

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13436 KB Output is correct
2 Correct 17 ms 13464 KB Output is correct
3 Correct 15 ms 13388 KB Output is correct
4 Correct 15 ms 13388 KB Output is correct
5 Correct 15 ms 13388 KB Output is correct
6 Correct 15 ms 13388 KB Output is correct
7 Correct 21 ms 13388 KB Output is correct
8 Correct 16 ms 13400 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 15 ms 13388 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13436 KB Output is correct
2 Correct 17 ms 13464 KB Output is correct
3 Correct 15 ms 13388 KB Output is correct
4 Correct 15 ms 13388 KB Output is correct
5 Correct 15 ms 13388 KB Output is correct
6 Correct 15 ms 13388 KB Output is correct
7 Correct 21 ms 13388 KB Output is correct
8 Correct 16 ms 13400 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 15 ms 13388 KB Output is correct
11 Correct 102 ms 43616 KB Output is correct
12 Correct 130 ms 43508 KB Output is correct
13 Correct 108 ms 43520 KB Output is correct
14 Correct 101 ms 43528 KB Output is correct
15 Correct 104 ms 43688 KB Output is correct
16 Correct 111 ms 43520 KB Output is correct
17 Correct 103 ms 43520 KB Output is correct
18 Correct 105 ms 43528 KB Output is correct
19 Correct 103 ms 43564 KB Output is correct
20 Correct 108 ms 43572 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13436 KB Output is correct
2 Correct 17 ms 13464 KB Output is correct
3 Correct 15 ms 13388 KB Output is correct
4 Correct 15 ms 13388 KB Output is correct
5 Correct 15 ms 13388 KB Output is correct
6 Correct 15 ms 13388 KB Output is correct
7 Correct 21 ms 13388 KB Output is correct
8 Correct 16 ms 13400 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 15 ms 13388 KB Output is correct
11 Correct 102 ms 43616 KB Output is correct
12 Correct 130 ms 43508 KB Output is correct
13 Correct 108 ms 43520 KB Output is correct
14 Correct 101 ms 43528 KB Output is correct
15 Correct 104 ms 43688 KB Output is correct
16 Correct 111 ms 43520 KB Output is correct
17 Correct 103 ms 43520 KB Output is correct
18 Correct 105 ms 43528 KB Output is correct
19 Correct 103 ms 43564 KB Output is correct
20 Correct 108 ms 43572 KB Output is correct
21 Correct 570 ms 136276 KB Output is correct
22 Correct 536 ms 136328 KB Output is correct
23 Correct 549 ms 136368 KB Output is correct
24 Correct 548 ms 136240 KB Output is correct
25 Correct 539 ms 136336 KB Output is correct
26 Correct 579 ms 136284 KB Output is correct
27 Correct 544 ms 136268 KB Output is correct
28 Correct 530 ms 136256 KB Output is correct
29 Correct 540 ms 136236 KB Output is correct
30 Correct 556 ms 136252 KB Output is correct