oj.uz

Submission #446108

# Submission time Handle Problem Language Result Execution time Memory
446108 2021-07-21T00:05:22 Z JovanB Index (COCI21_index) C++17
110 / 110
 348 ms 54608 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXC = 10000000;
const int MAXN = 200000;

struct Segment{
    int L, R, val;
} seg[MAXC];

int idxx;

void init(int node, int l, int r){
    if(l == r) return;
    int mid = (l+r)/2;
    seg[node].L = ++idxx;
    seg[node].R = ++idxx;
    init(seg[node].L, l, mid);
    init(seg[node].R, mid+1, r);
}

void upd(int node, int pnode, int l, int r, int x){
    if(l == r){
        seg[node].val = seg[pnode].val + 1;
        return;
    }
    int mid = (l+r)/2;
    seg[node].L = seg[pnode].L;
    seg[node].R = seg[pnode].R;
    if(x <= mid){
        seg[node].L = ++idxx;
        upd(seg[node].L, seg[pnode].L, l, mid, x);
    }
    else{
        seg[node].R = ++idxx;
        upd(seg[node].R, seg[pnode].R, mid+1, r, x);
    }
    seg[node].val = seg[seg[node].L].val + seg[seg[node].R].val;
}

int root[MAXN+5];

int query(int node, int pnode, int l, int r, int ost){
    if(l == r) return l;
    int mid = (l+r)/2;
    if(seg[seg[node].R].val - seg[seg[pnode].R].val + ost >= mid+1) return query(seg[node].R, seg[pnode].R, mid+1, r, ost);
    return query(seg[node].L, seg[pnode].L, l, mid, ost + seg[seg[node].R].val - seg[seg[pnode].R].val);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, qrs;
    cin >> n >> qrs;
    idxx = 1;
    root[0] = 1;
    init(1, 1, n);
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        root[i] = root[i-1];
        int old = root[i];
        root[i] = ++idxx;
        upd(root[i], old, 1, n, x);
    }
    while(qrs--){
        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 456 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 456 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 56 ms 12484 KB Output is correct
12 Correct 58 ms 12532 KB Output is correct
13 Correct 56 ms 12580 KB Output is correct
14 Correct 55 ms 12480 KB Output is correct
15 Correct 56 ms 12528 KB Output is correct
16 Correct 54 ms 12480 KB Output is correct
17 Correct 56 ms 12520 KB Output is correct
18 Correct 54 ms 12556 KB Output is correct
19 Correct 56 ms 12560 KB Output is correct
20 Correct 54 ms 12500 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 456 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 56 ms 12484 KB Output is correct
12 Correct 58 ms 12532 KB Output is correct
13 Correct 56 ms 12580 KB Output is correct
14 Correct 55 ms 12480 KB Output is correct
15 Correct 56 ms 12528 KB Output is correct
16 Correct 54 ms 12480 KB Output is correct
17 Correct 56 ms 12520 KB Output is correct
18 Correct 54 ms 12556 KB Output is correct
19 Correct 56 ms 12560 KB Output is correct
20 Correct 54 ms 12500 KB Output is correct
21 Correct 340 ms 53972 KB Output is correct
22 Correct 339 ms 54468 KB Output is correct
23 Correct 348 ms 54460 KB Output is correct
24 Correct 336 ms 54452 KB Output is correct
25 Correct 341 ms 54552 KB Output is correct
26 Correct 324 ms 54484 KB Output is correct
27 Correct 333 ms 54456 KB Output is correct
28 Correct 322 ms 54468 KB Output is correct
29 Correct 326 ms 54608 KB Output is correct
30 Correct 347 ms 54548 KB Output is correct