제출 #1286037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286037		gustavoml	Index (COCI21_index)	C++20	110 / 110	328 ms	134356 KiB

index

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define int long long

typedef long long ll;
typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 2e5 + 10;

struct Vertex {
    Vertex *l, *r;
    int sum;

    Vertex(int v) : l(nullptr), r(nullptr), sum(v) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
        if(l) sum += l->sum;
        if(r) sum += r->sum;
    }
};

Vertex* build(int begin = 0, int end = MAX) {
    if(begin == end) return new Vertex(0);
    int m = (begin + end) >> 1;
    return new Vertex(build(begin, m), build(m + 1, end));
}

Vertex* update(Vertex* v, int index, int add, int begin = 0, int end = MAX) {
    if(begin == end) return new Vertex(v->sum + add);
    int m = (begin + end) >> 1;
    if(index <= m) return new Vertex(update(v->l, index, add, begin, m), v->r);
    else return new Vertex(v->l, update(v->r, index, add, m + 1, end));
}

int query(Vertex* vl, Vertex *vr, int suffix, int begin = 0, int end = MAX) {
    if(begin == end) return begin;
    int right = vr->r->sum - vl->r->sum + suffix;
    int m = (begin + end) >> 1;
    if(right > m) return query(vl->r, vr->r, suffix, m + 1, end);
    return query(vl->l, vr->l, right, begin, m);
}

int32_t main() { _
    int n, q; cin >> n >> q;
    vector<int> p(n);
    for(int & i : p) cin >> i;
    vector<Vertex*> roots;
    roots.push_back(build());
    for(int i = 0; i < n; i++) {
        roots.push_back(update(roots.back(), p[i], 1));
    }
    while(q--) {
        int l, r; cin >> l >> r;
        cout << query(roots[l-1], roots[r], 0) << endl;
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50