Submission #446108

#	Time	Username	Problem	Language	Result	Execution time	Memory
446108		JovanB	Index (COCI21_index)	C++17	110 / 110	348 ms	54608 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50