Submission #698386

#	Time	Username	Problem	Language	Result	Execution time	Memory
698386		lukadupli	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	1164 ms	49956 KiB

Main

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1 << 18, MAXQ = 1e6 + 5;

struct TourSum
{
    int nodes[2 * MAXN];

    void update(int ind, int val, int node = 1, int l = 0, int r = MAXN){
        if(r - l == 1){
            nodes[node] = val;
            return;
        }

        int m = (l + r) / 2;
        if(ind < m) update(ind, val, 2 * node, l, m);
        else update(ind, val, 2 * node + 1, m, r);

        nodes[node] = nodes[2 * node] + nodes[2 * node + 1];
    }

    int binsearch(int val, int node = 1, int l = 0, int r = MAXN){
        if(r - l == 1) return l;

        int m = (l + r) / 2;

        if(nodes[2 * node] >= val) return binsearch(val, 2 * node, l, m);
        return binsearch(val - nodes[2 * node], 2 * node + 1, m, r);
    }

    int query(int lq, int rq, int node = 1, int l = 0, int r = MAXN){
        if(l >= lq && r <= rq) return nodes[node];
        if(l >= rq || r <= lq) return 0;

        int m = (l + r) / 2;
        return query(lq, rq, 2 * node, l, m) + query(lq, rq, 2 * node + 1, m, r);
    }
};

int n, q, arr[MAXN], pos[MAXN], maxrt[MAXN];
set<int> posset;
TourSum tour;

vector<pair<pii, int>> qs;
int sol[MAXQ];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        pos[arr[i]] = i;
    }

    posset.insert(n + 1);
    for(int i = n; i >= 1; i--){
        maxrt[pos[i]] = *posset.lower_bound(pos[i]);
        posset.insert(pos[i]);
    }

    for(int i = 1; i <= n; i = maxrt[i]){
        tour.update(arr[i], maxrt[i] - i);
    }

    for(int i = 0; i < q; i++){
        int t, p;
        cin >> t >> p;

        qs.push_back({{t, p}, i});
    }

    sort(qs.begin(), qs.end());
    int qpos = 0;
    for(int t = 0; t <= n; t++){
        while(qpos < qs.size() && qs[qpos].f.f == t){
            int num = tour.binsearch(qs[qpos].f.s);
            sol[qs[qpos].s] = arr[pos[num] + qs[qpos].f.s - tour.query(0, num) - 1];

            qpos++;
        }
        if(qpos == qs.size()) break;

        int num = tour.binsearch(n / 2);
        int realpos = tour.query(0, num) + 1;
        int amount = tour.nodes[MAXN + num];

        if(realpos + amount == n / 2 + 1) break;

        tour.update(num, n / 2 + 1 - realpos);

        for(int i = pos[num] + n / 2 + 1 - realpos; i < pos[num] + amount; i = maxrt[i])
            tour.update(arr[i], min(maxrt[i], pos[num] + amount) - i);
    }

    while(qpos < qs.size()){
        int num = tour.binsearch(qs[qpos].f.s);
        sol[qs[qpos].s] = arr[pos[num] + qs[qpos].f.s - tour.query(0, num) - 1];

        qpos++;
    }

    for(int i = 0; i < q; i++) cout << sol[i] << '\n';

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while(qpos < qs.size() && qs[qpos].f.f == t){
      |               ~~~~~^~~~~~~~~~~
Main.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         if(qpos == qs.size()) break;
      |            ~~~~~^~~~~~~~~~~~
Main.cpp:102:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     while(qpos < qs.size()){
      |           ~~~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25