oj.uz

Submission #698355

# Submission time Handle Problem Language Result Execution time Memory
698355 2023-02-13T09:26:40 Z lukadupli Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 927 ms 30624 KB 
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1 << 18;

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[MAXN];

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], maxrt[i] - i);
    }

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

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

	return 0;
}

Compilation message

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:101:25: 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]
  101 |     for(int i = qpos; i < qs.size(); i++){
      |                       ~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 680 ms 20736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 927 ms 30624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 10596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 680 ms 20736 KB Output isn't correct
2 Halted 0 ms 0 KB -