Submission #476211

#	Time	Username	Problem	Language	Result	Execution time	Memory
476211		Shin	Index (COCI21_index)	C++14	110 / 110	579 ms	136368 KiB

index

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct Node {
    int val;
    Node *l = NULL, *r = NULL;

    Node(int _val = 0) : val(_val) {};
    Node(Node *ll, Node *rr) : l(ll), r(rr) {
        val = (l ? l->val : 0) + (r ? r->val : 0);
    }
};

struct P_IT {
    vector<Node*> root;
    int n;

    P_IT(int _n = 0) : n(_n) {
        root.push_back(build(1, n));
    }
    
    Node* build(int l, int r) {
        if (l == r) return new Node();
        int mid = (l + r) >> 1;
        return new Node(build(l, mid), build(mid + 1, r));
    }

    Node* update(Node* node, int pos, int val, int l, int r) {
        if (l == r) return new Node(node->val + val);
        int mid = (l + r) >> 1;
        if (mid < pos) return new Node(node->l, update(node->r, pos, val, mid + 1, r));
        return new Node (update(node->l, pos, val, l, mid), node->r);
    }

    int get(Node* ll, Node* rr, int sum, int l, int r) {
        if (l == r) return l;
        int mid = (l + r) >> 1, delta = rr->r->val - ll->r->val;
        if (mid >= delta + sum) return get(ll->l, rr->l, sum + delta, l, mid);
        return get(ll->r, rr->r, sum, mid + 1, r);
    }

    void update(int pos, int val) {
        root.push_back(update(root.back(), pos, val, 1, n));
    }

    int query(int l, int r) {
        return get(root[l - 1], root[r], 0, 1, n);
    }
};

void solve(void) { 
    int n, q; cin >> n >> q;
    P_IT st(N);
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        st.update(x, 1);
    }

    while (q --) {
        int l, r; cin >> l >> r;
        cout << st.query(l, r) << '\n';
    }
} 

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

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