oj.uz

Submission #675961

# Submission time Handle Problem Language Result Execution time Memory
675961 2022-12-28T16:28:38 Z MrBrionix Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1491 ms 50584 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
  
    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;
    }
}
 
// build treap for [l,r)
node* build(vector<T>& A, int l, int r) {
  if (l + 1 == r) return 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);
}
 
 
const int MAXN = 200005, MAXQ = 1000006;
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);
		}
		
		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:31:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |   if (!a) return b; a->fix();
      |   ^~
Main.cpp:31:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |   if (!a) return b; a->fix();
      |                     ^
Main.cpp:32:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |   if (!b) return a; b->fix();
      |   ^~
Main.cpp:32:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   32 |   if (!b) return a; b->fix();
      |                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 28036 KB Output is correct
2 Correct 279 ms 27688 KB Output is correct
3 Correct 256 ms 26828 KB Output is correct
4 Correct 247 ms 27452 KB Output is correct
5 Correct 277 ms 29860 KB Output is correct
6 Correct 258 ms 29652 KB Output is correct
7 Correct 302 ms 29584 KB Output is correct
8 Correct 247 ms 27852 KB Output is correct
9 Correct 253 ms 27140 KB Output is correct
10 Correct 254 ms 26860 KB Output is correct
11 Correct 251 ms 26768 KB Output is correct
12 Correct 251 ms 24864 KB Output is correct
13 Correct 243 ms 25544 KB Output is correct
14 Correct 266 ms 29364 KB Output is correct
15 Correct 255 ms 27516 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 243 ms 25532 KB Output is correct
18 Correct 265 ms 25476 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 620 ms 47292 KB Output is correct
2 Correct 445 ms 46208 KB Output is correct
3 Correct 417 ms 39468 KB Output is correct
4 Correct 409 ms 37756 KB Output is correct
5 Correct 433 ms 38448 KB Output is correct
6 Correct 477 ms 38832 KB Output is correct
7 Correct 471 ms 42392 KB Output is correct
8 Correct 464 ms 43156 KB Output is correct
9 Correct 412 ms 38060 KB Output is correct
10 Correct 432 ms 41564 KB Output is correct
11 Correct 356 ms 36340 KB Output is correct
12 Correct 362 ms 35756 KB Output is correct
13 Correct 400 ms 41372 KB Output is correct
14 Correct 407 ms 39280 KB Output is correct
15 Correct 468 ms 44192 KB Output is correct
16 Correct 105 ms 16144 KB Output is correct
17 Correct 450 ms 39608 KB Output is correct
18 Correct 320 ms 34432 KB Output is correct
19 Correct 176 ms 20804 KB Output is correct
20 Correct 193 ms 21464 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 14868 KB Output is correct
2 Correct 148 ms 13896 KB Output is correct
3 Correct 181 ms 14088 KB Output is correct
4 Correct 144 ms 13468 KB Output is correct
5 Correct 188 ms 13780 KB Output is correct
6 Correct 156 ms 13564 KB Output is correct
7 Correct 181 ms 13588 KB Output is correct
8 Correct 154 ms 13240 KB Output is correct
9 Correct 179 ms 14008 KB Output is correct
10 Correct 157 ms 13280 KB Output is correct
11 Correct 107 ms 13112 KB Output is correct
12 Correct 138 ms 13368 KB Output is correct
13 Correct 155 ms 13440 KB Output is correct
14 Correct 116 ms 13592 KB Output is correct
15 Correct 131 ms 12924 KB Output is correct
16 Correct 54 ms 10364 KB Output is correct
17 Correct 142 ms 12588 KB Output is correct
18 Correct 113 ms 12564 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 28036 KB Output is correct
2 Correct 279 ms 27688 KB Output is correct
3 Correct 256 ms 26828 KB Output is correct
4 Correct 247 ms 27452 KB Output is correct
5 Correct 277 ms 29860 KB Output is correct
6 Correct 258 ms 29652 KB Output is correct
7 Correct 302 ms 29584 KB Output is correct
8 Correct 247 ms 27852 KB Output is correct
9 Correct 253 ms 27140 KB Output is correct
10 Correct 254 ms 26860 KB Output is correct
11 Correct 251 ms 26768 KB Output is correct
12 Correct 251 ms 24864 KB Output is correct
13 Correct 243 ms 25544 KB Output is correct
14 Correct 266 ms 29364 KB Output is correct
15 Correct 255 ms 27516 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 243 ms 25532 KB Output is correct
18 Correct 265 ms 25476 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 620 ms 47292 KB Output is correct
22 Correct 445 ms 46208 KB Output is correct
23 Correct 417 ms 39468 KB Output is correct
24 Correct 409 ms 37756 KB Output is correct
25 Correct 433 ms 38448 KB Output is correct
26 Correct 477 ms 38832 KB Output is correct
27 Correct 471 ms 42392 KB Output is correct
28 Correct 464 ms 43156 KB Output is correct
29 Correct 412 ms 38060 KB Output is correct
30 Correct 432 ms 41564 KB Output is correct
31 Correct 356 ms 36340 KB Output is correct
32 Correct 362 ms 35756 KB Output is correct
33 Correct 400 ms 41372 KB Output is correct
34 Correct 407 ms 39280 KB Output is correct
35 Correct 468 ms 44192 KB Output is correct
36 Correct 105 ms 16144 KB Output is correct
37 Correct 450 ms 39608 KB Output is correct
38 Correct 320 ms 34432 KB Output is correct
39 Correct 176 ms 20804 KB Output is correct
40 Correct 193 ms 21464 KB Output is correct
41 Correct 263 ms 14868 KB Output is correct
42 Correct 148 ms 13896 KB Output is correct
43 Correct 181 ms 14088 KB Output is correct
44 Correct 144 ms 13468 KB Output is correct
45 Correct 188 ms 13780 KB Output is correct
46 Correct 156 ms 13564 KB Output is correct
47 Correct 181 ms 13588 KB Output is correct
48 Correct 154 ms 13240 KB Output is correct
49 Correct 179 ms 14008 KB Output is correct
50 Correct 157 ms 13280 KB Output is correct
51 Correct 107 ms 13112 KB Output is correct
52 Correct 138 ms 13368 KB Output is correct
53 Correct 155 ms 13440 KB Output is correct
54 Correct 116 ms 13592 KB Output is correct
55 Correct 131 ms 12924 KB Output is correct
56 Correct 54 ms 10364 KB Output is correct
57 Correct 142 ms 12588 KB Output is correct
58 Correct 113 ms 12564 KB Output is correct
59 Correct 3 ms 4948 KB Output is correct
60 Correct 3 ms 4948 KB Output is correct
61 Correct 1491 ms 50584 KB Output is correct
62 Correct 1047 ms 49112 KB Output is correct
63 Correct 1149 ms 46696 KB Output is correct
64 Correct 1133 ms 46360 KB Output is correct
65 Correct 1171 ms 49004 KB Output is correct
66 Correct 1091 ms 46252 KB Output is correct
67 Correct 946 ms 45980 KB Output is correct
68 Correct 951 ms 45080 KB Output is correct
69 Correct 1048 ms 46412 KB Output is correct
70 Correct 855 ms 43904 KB Output is correct
71 Correct 764 ms 44984 KB Output is correct
72 Correct 873 ms 42592 KB Output is correct
73 Correct 746 ms 43508 KB Output is correct
74 Correct 857 ms 46480 KB Output is correct
75 Correct 979 ms 43328 KB Output is correct
76 Correct 107 ms 15784 KB Output is correct
77 Correct 794 ms 38596 KB Output is correct
78 Correct 724 ms 39676 KB Output is correct
79 Correct 2 ms 4948 KB Output is correct
80 Correct 3 ms 5036 KB Output is correct