Submission #698361

#TimeUsernameProblemLanguageResultExecution timeMemory
698361lukadupliAbracadabra (CEOI22_abracadabra)C++14
0 / 100
987 ms27044 KiB
#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], 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 (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: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++){
      |                       ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...