oj.uz

Submission #638645

# Submission time Handle Problem Language Result Execution time Memory
638645 2022-09-06T15:24:21 Z HaYoungJoon Index (COCI21_index) C++14
110 / 110
 1758 ms 54684 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 1;

struct Node {
    int val,Lid,Rid;
    Node() {};
    Node(int val, int L, int R): val(val), Lid(L), Rid(R) {}
} t[21*maxn];

int n,Q, root[maxn + 1], nNode = 0, version = 0;

int build(int tl, int tr) {
    int cur = ++nNode;
    if (tl == tr) t[cur] = Node(0,0,0);
    else {
        int tm = (tl + tr)/2;
        t[cur].val = 0;
        t[cur].Lid = build(tl,tm);
        t[cur].Rid = build(tm+1,tr);
    }
    return cur;
}
int update(int oldID, int tl, int tr, int pos) {
    if (tl == tr) {
        ++nNode;
        t[nNode] = Node(t[oldID].val + 1,0,0);
        return nNode;
    }
    int tm = (tl + tr)/2;
    int cur = ++nNode;
 //   assert(cur < 11*maxn);
    if (pos <= tm) {
        t[cur].Lid = update(t[oldID].Lid,tl,tm,pos);
        t[cur].Rid = t[oldID].Rid;
        t[cur].val = t[t[cur].Lid].val + t[t[cur].Rid].val;
    } else {
        t[cur].Rid = update(t[oldID].Rid,tm+1,tr,pos);
        t[cur].Lid = t[oldID].Lid;
        t[cur].val = t[t[cur].Lid].val + t[t[cur].Rid].val;
    }
    return cur;
}

int get(int cur, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return 0;
    if (tl >= l && tr <= r) return t[cur].val;
    int tm = (tl + tr)/2;
    return get(t[cur].Lid,tl,tm,l,r) + get(t[cur].Rid,tm+1,tr,l,r);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Q;
    root[0] = build(1,maxn - 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        ++version;
        root[version] = update(root[version-1],1,maxn-1,x);
    }
 //   cout << nNode << '\n';
    while (Q--) {
        int l,r;
        cin >> l >> r;
        int res = 0, L = 1, R = r - l + 1;
        while (L <= R) {
            int mid = (L + R)/2;
            if (get(root[r],1,maxn-1,mid,maxn-1) - get(root[l-1],1,maxn-1,mid,maxn-1) >= mid) {
                res = mid;
                L = mid+1;
            } else R = mid-1;
        }
        printf("%d\n",res);
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5204 KB Output is correct
2 Correct 8 ms 5160 KB Output is correct
3 Correct 7 ms 5272 KB Output is correct
4 Correct 7 ms 5176 KB Output is correct
5 Correct 8 ms 5204 KB Output is correct
6 Correct 7 ms 5204 KB Output is correct
7 Correct 7 ms 5204 KB Output is correct
8 Correct 8 ms 5204 KB Output is correct
9 Correct 9 ms 5204 KB Output is correct
10 Correct 8 ms 5172 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5204 KB Output is correct
2 Correct 8 ms 5160 KB Output is correct
3 Correct 7 ms 5272 KB Output is correct
4 Correct 7 ms 5176 KB Output is correct
5 Correct 8 ms 5204 KB Output is correct
6 Correct 7 ms 5204 KB Output is correct
7 Correct 7 ms 5204 KB Output is correct
8 Correct 8 ms 5204 KB Output is correct
9 Correct 9 ms 5204 KB Output is correct
10 Correct 8 ms 5172 KB Output is correct
11 Correct 296 ms 17276 KB Output is correct
12 Correct 302 ms 17240 KB Output is correct
13 Correct 296 ms 17292 KB Output is correct
14 Correct 252 ms 17224 KB Output is correct
15 Correct 283 ms 17376 KB Output is correct
16 Correct 288 ms 17212 KB Output is correct
17 Correct 250 ms 17228 KB Output is correct
18 Correct 281 ms 17308 KB Output is correct
19 Correct 280 ms 17228 KB Output is correct
20 Correct 252 ms 17216 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5204 KB Output is correct
2 Correct 8 ms 5160 KB Output is correct
3 Correct 7 ms 5272 KB Output is correct
4 Correct 7 ms 5176 KB Output is correct
5 Correct 8 ms 5204 KB Output is correct
6 Correct 7 ms 5204 KB Output is correct
7 Correct 7 ms 5204 KB Output is correct
8 Correct 8 ms 5204 KB Output is correct
9 Correct 9 ms 5204 KB Output is correct
10 Correct 8 ms 5172 KB Output is correct
11 Correct 296 ms 17276 KB Output is correct
12 Correct 302 ms 17240 KB Output is correct
13 Correct 296 ms 17292 KB Output is correct
14 Correct 252 ms 17224 KB Output is correct
15 Correct 283 ms 17376 KB Output is correct
16 Correct 288 ms 17212 KB Output is correct
17 Correct 250 ms 17228 KB Output is correct
18 Correct 281 ms 17308 KB Output is correct
19 Correct 280 ms 17228 KB Output is correct
20 Correct 252 ms 17216 KB Output is correct
21 Correct 1720 ms 54536 KB Output is correct
22 Correct 1631 ms 54656 KB Output is correct
23 Correct 1637 ms 54568 KB Output is correct
24 Correct 1743 ms 54648 KB Output is correct
25 Correct 1758 ms 54532 KB Output is correct
26 Correct 1690 ms 54476 KB Output is correct
27 Correct 1688 ms 54512 KB Output is correct
28 Correct 1734 ms 54596 KB Output is correct
29 Correct 1749 ms 54684 KB Output is correct
30 Correct 1724 ms 54476 KB Output is correct