oj.uz

Submission #486220

# Submission time Handle Problem Language Result Execution time Memory
486220 2021-11-11T02:44:51 Z diedie Index (COCI21_index) C++17
110 / 110
 299 ms 51012 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi32 = pair<int, int>;
using pi64 = pair<int64_t, int64_t>;

const int maxN = 2e5 + 5;
const int maxC = 10000000;
const ll INF = 2e18 + 7;
const int MOD = 998244353;

int n, nTest;
int idx;

struct Segment {
    int left, right, val;
} st[maxC];

void init (int id, int l, int r){
    if (l == r) return;

    int mid = (l + r) / 2;
    st[id].left = ++idx;
    st[id].right = ++idx;
    init(st[id].left, l, mid);
    init(st[id].right, mid + 1, r);
}

void update (int id, int pos, int l, int r, int h) {
    if (l == r) {
        st[id].val = st[pos].val + 1;
        return;
    }

    int mid = (l + r) / 2;
    st[id].left = st[pos].left;
    st[id].right = st[pos].right;
    if (h <= mid) {
        st[id].left = ++idx;
        update(st[id].left, st[pos].left, l, mid, h);
    }
    else {
        st[id].right = ++idx;
        update(st[id].right, st[pos].right, mid + 1, r, h);
    }
    st[id].val = st[st[id].left].val + st[st[id].right].val;
}

int root[maxN];

int query (int id, int pos, int l, int r, int add) {
    if (l == r) return l;

    int mid = (l + r) / 2;
    int tmp = st[st[id].right].val - st[st[pos].right].val + add;
    if (tmp >= mid + 1)
        return query(st[id].right, st[pos].right, mid + 1, r, add);
    else return query(st[id].left, st[pos].left, l, mid, tmp);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> nTest;
    idx = 1;
    root[0] = 1;
    init(1, 1, n);
    for (int i = 1; i <= n; ++i) {
        int h; cin >> h;
        root[i] = root[i - 1];
        int old = root[i];
        root[i] = ++idx;
        update(root[i], old, 1, n, h);
    }

    while (nTest--) {
        int l, r; cin >> l >> r;
        cout << query(root[r], root[l-1], 1, n, 0) << '\n';
    }

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 45 ms 11844 KB Output is correct
12 Correct 46 ms 11904 KB Output is correct
13 Correct 49 ms 11868 KB Output is correct
14 Correct 42 ms 11888 KB Output is correct
15 Correct 42 ms 11804 KB Output is correct
16 Correct 55 ms 11844 KB Output is correct
17 Correct 43 ms 11876 KB Output is correct
18 Correct 41 ms 11852 KB Output is correct
19 Correct 44 ms 11896 KB Output is correct
20 Correct 43 ms 11988 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 45 ms 11844 KB Output is correct
12 Correct 46 ms 11904 KB Output is correct
13 Correct 49 ms 11868 KB Output is correct
14 Correct 42 ms 11888 KB Output is correct
15 Correct 42 ms 11804 KB Output is correct
16 Correct 55 ms 11844 KB Output is correct
17 Correct 43 ms 11876 KB Output is correct
18 Correct 41 ms 11852 KB Output is correct
19 Correct 44 ms 11896 KB Output is correct
20 Correct 43 ms 11988 KB Output is correct
21 Correct 244 ms 50896 KB Output is correct
22 Correct 299 ms 51012 KB Output is correct
23 Correct 244 ms 50900 KB Output is correct
24 Correct 259 ms 50992 KB Output is correct
25 Correct 244 ms 50932 KB Output is correct
26 Correct 252 ms 50916 KB Output is correct
27 Correct 260 ms 50988 KB Output is correct
28 Correct 285 ms 50888 KB Output is correct
29 Correct 277 ms 50964 KB Output is correct
30 Correct 279 ms 50884 KB Output is correct