oj.uz

Submission #675962

# Submission time Handle Problem Language Result Execution time Memory
675962 2022-12-28T16:31:35 Z MrBrionix Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1614 ms 45012 KB 
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(0);//rng(time(nullptr));
 
using T = int;
struct node {
    T val, ma;
    int size;
    size_t prior;
    node *left, *right;
	node *par=nullptr; bool isleft=0; //se serve get_pos
    bool rot = false;
  
    node(T v) : val(v), ma(v), size(1),
             prior(rng()), left(0), right(0) {}
 
    node* fix() {
        ma = val, size = 1;
        if (left) {
            ma = max(ma, left->ma);
            size += left->size;
        }
        if (right) {
            ma = max(ma, right->ma);
            size += right->size;
        }
        return this;
    }
};
 
node* merge(node* a, node* b) {
  if (!a) return b; a->fix();
  if (!b) return a; b->fix();
  if (a->prior > b->prior) {
    auto tmp = merge(a->right, b);
    a->right = tmp;
    if(tmp)tmp->par = a, tmp->isleft = 0; //x get_pos
    return a->fix();
  } else {
    auto tmp = merge(a, b->left);
    b->left = tmp;
    if(tmp)tmp->par = b, tmp->isleft = 1; //x get_pos
    return b->fix();
  }
}
//taglio subito dopo k elementi (1-based)
//es. k=1, divido il primo elemento dagli altri
pair<node*, node*> split(node* p, int k) {
  if (!p) return {nullptr, nullptr};
  p->fix();
  int sl = p->left ? p->left->size : 0;
  if (k <= sl) {
    auto [a, b] = split(p->left, k);
    if(a) a->par = nullptr, a->isleft=0; //per get_pos
    p->left = b;
    if(b) b->par = p, b->isleft = 1; //per get_pos
    return {a, p->fix()};
  } else {
    auto [a, b] = split(p->right, k-sl-1);
    if(b) b->par = nullptr, b->isleft=0; //per get_pos
    p->right = a;
    if(a) a->par = p, a->isleft = 0; //per get_pos
    return {p->fix(), b};
  }//invariante: sui due nodi di ritorno
}  //è sempre stata chiamata ->fix()
 
// ritorna il k-esimo nodo (0-based)
int find_kth(node* p,int pos){
  int sl = p->left ? p->left->size : 0;
  if (p->left && pos < sl) {
    return find_kth(p->left,pos);
  } else if (p->right && pos > sl) {
    return find_kth(p->right,pos - sl - 1);
  } else {
    return p->val;
  }
}
 
int find_first(node *p,int val){
    int sl = p->left ? p->left->size : 0;
    if (p->left && p->left->ma > val) {
        return find_first(p->left,val);
    } else if (p->val > val){
		return sl;
	} else if (p->right && p->right->ma > val) {
        return sl + 1 + find_first(p->right,val);
    } else {
        return p->size;
    }
}
 
const int MAXN = 200005, MAXQ = 1000006;
node* vv[MAXN];
node* build(vector<T>& A, int l, int r) {
  if (l + 1 == r) return vv[A[l]] = new node(A[l]);
  int m = (l + r) / 2;
  node* a = build(A, l, m);
  node* b = build(A, m, r);
  return merge(a, b);
}
 
// dato un node* p, ritorna la sua posizione (0-based)
int get_pos(node* p){ //modificare split/merge
  if(!p)return -1;  //decommentando le righe x get_pos
  bool flag = (p->par && p->par->rot);
  if(p->isleft ^ flag){
    int rightsize=0;
    if(p->right)rightsize=p->right->size;
    return get_pos(p->par)-rightsize-1;
  }else{
    int leftsize=0;
    if(p->left)leftsize=p->left->size;
    return get_pos(p->par)+leftsize+1;
  }
}
 
int n,q,ans[MAXQ],tmp[MAXN],cont;
vector<T> v;
vector<pair<int,int> > opz[MAXN];
node* root;
 
int main(){
 
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	cin>>n>>q;
	v.resize(n);
	
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	
	for(int i=0;i<q;i++){
		int t,x;
		cin>>t>>x;
		opz[min(t,n)].emplace_back(x-1,i);
	}
	root = build(v,0,n);
	
	for(int i=0;i<=n;i++){
		for(auto [a,b] : opz[i]){
			ans[b]=find_kth(root,a);
          	assert(get_pos(vv[ans[b]])==a);
		}
		
		auto [a,b] = split(root,n/2);
		
		while(b!=nullptr){
			int val = find_kth(b,0);
			
			if(val > a->ma){
				a = merge(a,b);
				break;
			}
			
			int pos1 = find_first(a,val);
			int pos2 = find_first(b,val);
			
			auto [c,d] = split(b,pos2);
			auto [e,f] = split(a,pos1);
			
			a = merge(merge(e,c),f);
			b = d;
			cont++;
		}
		root = a;
	}
 
	for(int i=0;i<q;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

Compilation message

Main.cpp: In function 'node* merge(node*, node*)':
Main.cpp:32:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |   if (!a) return b; a->fix();
      |   ^~
Main.cpp:32:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   32 |   if (!a) return b; a->fix();
      |                     ^
Main.cpp:33:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |   if (!b) return a; b->fix();
      |   ^~
Main.cpp:33:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |   if (!b) return a; b->fix();
      |                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 23808 KB Output is correct
2 Correct 324 ms 22668 KB Output is correct
3 Correct 309 ms 22344 KB Output is correct
4 Correct 310 ms 21960 KB Output is correct
5 Correct 308 ms 24576 KB Output is correct
6 Correct 302 ms 24880 KB Output is correct
7 Correct 312 ms 24948 KB Output is correct
8 Correct 289 ms 23372 KB Output is correct
9 Correct 294 ms 22368 KB Output is correct
10 Correct 292 ms 22120 KB Output is correct
11 Correct 302 ms 22580 KB Output is correct
12 Correct 287 ms 20756 KB Output is correct
13 Correct 301 ms 21548 KB Output is correct
14 Correct 326 ms 23704 KB Output is correct
15 Correct 301 ms 21876 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 290 ms 20936 KB Output is correct
18 Correct 290 ms 20732 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 38784 KB Output is correct
2 Correct 499 ms 38704 KB Output is correct
3 Correct 466 ms 34224 KB Output is correct
4 Correct 494 ms 34380 KB Output is correct
5 Correct 499 ms 35196 KB Output is correct
6 Correct 535 ms 33904 KB Output is correct
7 Correct 533 ms 38548 KB Output is correct
8 Correct 551 ms 37144 KB Output is correct
9 Correct 456 ms 34864 KB Output is correct
10 Correct 485 ms 37120 KB Output is correct
11 Correct 419 ms 34660 KB Output is correct
12 Correct 427 ms 33692 KB Output is correct
13 Correct 498 ms 37264 KB Output is correct
14 Correct 438 ms 34448 KB Output is correct
15 Correct 490 ms 37660 KB Output is correct
16 Correct 115 ms 20148 KB Output is correct
17 Correct 467 ms 37172 KB Output is correct
18 Correct 372 ms 33936 KB Output is correct
19 Correct 200 ms 23620 KB Output is correct
20 Correct 204 ms 23140 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 15864 KB Output is correct
2 Correct 179 ms 15260 KB Output is correct
3 Correct 190 ms 15180 KB Output is correct
4 Correct 161 ms 14844 KB Output is correct
5 Correct 219 ms 15584 KB Output is correct
6 Correct 161 ms 14888 KB Output is correct
7 Correct 178 ms 15304 KB Output is correct
8 Correct 171 ms 14788 KB Output is correct
9 Correct 185 ms 15228 KB Output is correct
10 Correct 141 ms 14500 KB Output is correct
11 Correct 128 ms 14908 KB Output is correct
12 Correct 163 ms 14744 KB Output is correct
13 Correct 133 ms 14416 KB Output is correct
14 Correct 135 ms 14844 KB Output is correct
15 Correct 135 ms 14736 KB Output is correct
16 Correct 51 ms 12756 KB Output is correct
17 Correct 122 ms 14248 KB Output is correct
18 Correct 134 ms 14240 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 23808 KB Output is correct
2 Correct 324 ms 22668 KB Output is correct
3 Correct 309 ms 22344 KB Output is correct
4 Correct 310 ms 21960 KB Output is correct
5 Correct 308 ms 24576 KB Output is correct
6 Correct 302 ms 24880 KB Output is correct
7 Correct 312 ms 24948 KB Output is correct
8 Correct 289 ms 23372 KB Output is correct
9 Correct 294 ms 22368 KB Output is correct
10 Correct 292 ms 22120 KB Output is correct
11 Correct 302 ms 22580 KB Output is correct
12 Correct 287 ms 20756 KB Output is correct
13 Correct 301 ms 21548 KB Output is correct
14 Correct 326 ms 23704 KB Output is correct
15 Correct 301 ms 21876 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 290 ms 20936 KB Output is correct
18 Correct 290 ms 20732 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 663 ms 38784 KB Output is correct
22 Correct 499 ms 38704 KB Output is correct
23 Correct 466 ms 34224 KB Output is correct
24 Correct 494 ms 34380 KB Output is correct
25 Correct 499 ms 35196 KB Output is correct
26 Correct 535 ms 33904 KB Output is correct
27 Correct 533 ms 38548 KB Output is correct
28 Correct 551 ms 37144 KB Output is correct
29 Correct 456 ms 34864 KB Output is correct
30 Correct 485 ms 37120 KB Output is correct
31 Correct 419 ms 34660 KB Output is correct
32 Correct 427 ms 33692 KB Output is correct
33 Correct 498 ms 37264 KB Output is correct
34 Correct 438 ms 34448 KB Output is correct
35 Correct 490 ms 37660 KB Output is correct
36 Correct 115 ms 20148 KB Output is correct
37 Correct 467 ms 37172 KB Output is correct
38 Correct 372 ms 33936 KB Output is correct
39 Correct 200 ms 23620 KB Output is correct
40 Correct 204 ms 23140 KB Output is correct
41 Correct 242 ms 15864 KB Output is correct
42 Correct 179 ms 15260 KB Output is correct
43 Correct 190 ms 15180 KB Output is correct
44 Correct 161 ms 14844 KB Output is correct
45 Correct 219 ms 15584 KB Output is correct
46 Correct 161 ms 14888 KB Output is correct
47 Correct 178 ms 15304 KB Output is correct
48 Correct 171 ms 14788 KB Output is correct
49 Correct 185 ms 15228 KB Output is correct
50 Correct 141 ms 14500 KB Output is correct
51 Correct 128 ms 14908 KB Output is correct
52 Correct 163 ms 14744 KB Output is correct
53 Correct 133 ms 14416 KB Output is correct
54 Correct 135 ms 14844 KB Output is correct
55 Correct 135 ms 14736 KB Output is correct
56 Correct 51 ms 12756 KB Output is correct
57 Correct 122 ms 14248 KB Output is correct
58 Correct 134 ms 14240 KB Output is correct
59 Correct 3 ms 4948 KB Output is correct
60 Correct 3 ms 5032 KB Output is correct
61 Correct 1614 ms 45012 KB Output is correct
62 Correct 1318 ms 42952 KB Output is correct
63 Correct 1322 ms 42060 KB Output is correct
64 Correct 1293 ms 41584 KB Output is correct
65 Correct 1541 ms 42892 KB Output is correct
66 Correct 1503 ms 41476 KB Output is correct
67 Correct 1305 ms 41052 KB Output is correct
68 Correct 1421 ms 39604 KB Output is correct
69 Correct 1451 ms 42116 KB Output is correct
70 Correct 1381 ms 39224 KB Output is correct
71 Correct 1343 ms 41128 KB Output is correct
72 Correct 1325 ms 39312 KB Output is correct
73 Correct 1215 ms 40360 KB Output is correct
74 Correct 1253 ms 41892 KB Output is correct
75 Correct 1266 ms 40180 KB Output is correct
76 Correct 121 ms 20268 KB Output is correct
77 Correct 1115 ms 37560 KB Output is correct
78 Correct 1108 ms 37380 KB Output is correct
79 Correct 3 ms 4948 KB Output is correct
80 Correct 3 ms 4948 KB Output is correct