oj.uz

Submission #674876

# Submission time Handle Problem Language Result Execution time Memory
674876 2022-12-26T12:32:27 Z MrBrionix Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1752 ms 47016 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; //se serve get_pos
        return a->fix();
    } else {
        auto tmp = merge(a, b->left);
        b->left = tmp;
        if(tmp)tmp->par = b, tmp->isleft = 1; //se serve 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; //se serve get_pos
        p->left = b;
        if(b) b->par = p, b->isleft = 1; //se serve get_pos
        return {a, p->fix()};
    } else {
        auto [a, b] = split(p->right, k-sl-1);
        if(b) b->par = nullptr, b->isleft=0; //se serve get_pos
        p->right = a;
        if(a) a->par = p, a->isleft = 0; //se serve get_pos
        return {p->fix(), b};
    }//invariante: sui due nodi di ritorno
}    //è sempre stata chiamata ->fix()
 
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){
    if(!p)return -1;
    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:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |     if (!a) return b; a->fix();
      |     ^~
Main.cpp:32:23: 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:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |     if (!b) return a; b->fix();
      |     ^~
Main.cpp:33:23: 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 326 ms 24976 KB Output is correct
2 Correct 340 ms 23968 KB Output is correct
3 Correct 318 ms 23424 KB Output is correct
4 Correct 303 ms 23184 KB Output is correct
5 Correct 325 ms 25908 KB Output is correct
6 Correct 303 ms 25996 KB Output is correct
7 Correct 324 ms 26212 KB Output is correct
8 Correct 300 ms 24620 KB Output is correct
9 Correct 320 ms 23696 KB Output is correct
10 Correct 306 ms 23544 KB Output is correct
11 Correct 318 ms 23716 KB Output is correct
12 Correct 305 ms 21928 KB Output is correct
13 Correct 313 ms 22816 KB Output is correct
14 Correct 337 ms 24964 KB Output is correct
15 Correct 321 ms 23160 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 293 ms 22436 KB Output is correct
18 Correct 290 ms 22140 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 674 ms 39944 KB Output is correct
2 Correct 546 ms 40024 KB Output is correct
3 Correct 472 ms 35508 KB Output is correct
4 Correct 498 ms 35780 KB Output is correct
5 Correct 556 ms 36544 KB Output is correct
6 Correct 555 ms 35356 KB Output is correct
7 Correct 578 ms 39944 KB Output is correct
8 Correct 619 ms 38480 KB Output is correct
9 Correct 544 ms 36400 KB Output is correct
10 Correct 526 ms 38692 KB Output is correct
11 Correct 506 ms 36664 KB Output is correct
12 Correct 500 ms 35664 KB Output is correct
13 Correct 524 ms 39336 KB Output is correct
14 Correct 512 ms 36348 KB Output is correct
15 Correct 570 ms 39672 KB Output is correct
16 Correct 128 ms 20828 KB Output is correct
17 Correct 559 ms 39264 KB Output is correct
18 Correct 427 ms 35892 KB Output is correct
19 Correct 244 ms 24912 KB Output is correct
20 Correct 215 ms 24412 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 17224 KB Output is correct
2 Correct 185 ms 16292 KB Output is correct
3 Correct 195 ms 16384 KB Output is correct
4 Correct 180 ms 15884 KB Output is correct
5 Correct 234 ms 16144 KB Output is correct
6 Correct 180 ms 15856 KB Output is correct
7 Correct 203 ms 16076 KB Output is correct
8 Correct 191 ms 15548 KB Output is correct
9 Correct 233 ms 16356 KB Output is correct
10 Correct 168 ms 15680 KB Output is correct
11 Correct 134 ms 15516 KB Output is correct
12 Correct 164 ms 15588 KB Output is correct
13 Correct 179 ms 15500 KB Output is correct
14 Correct 139 ms 15944 KB Output is correct
15 Correct 149 ms 15260 KB Output is correct
16 Correct 53 ms 12704 KB Output is correct
17 Correct 141 ms 14796 KB Output is correct
18 Correct 132 ms 14872 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 326 ms 24976 KB Output is correct
2 Correct 340 ms 23968 KB Output is correct
3 Correct 318 ms 23424 KB Output is correct
4 Correct 303 ms 23184 KB Output is correct
5 Correct 325 ms 25908 KB Output is correct
6 Correct 303 ms 25996 KB Output is correct
7 Correct 324 ms 26212 KB Output is correct
8 Correct 300 ms 24620 KB Output is correct
9 Correct 320 ms 23696 KB Output is correct
10 Correct 306 ms 23544 KB Output is correct
11 Correct 318 ms 23716 KB Output is correct
12 Correct 305 ms 21928 KB Output is correct
13 Correct 313 ms 22816 KB Output is correct
14 Correct 337 ms 24964 KB Output is correct
15 Correct 321 ms 23160 KB Output is correct
16 Correct 3 ms 5040 KB Output is correct
17 Correct 293 ms 22436 KB Output is correct
18 Correct 290 ms 22140 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 674 ms 39944 KB Output is correct
22 Correct 546 ms 40024 KB Output is correct
23 Correct 472 ms 35508 KB Output is correct
24 Correct 498 ms 35780 KB Output is correct
25 Correct 556 ms 36544 KB Output is correct
26 Correct 555 ms 35356 KB Output is correct
27 Correct 578 ms 39944 KB Output is correct
28 Correct 619 ms 38480 KB Output is correct
29 Correct 544 ms 36400 KB Output is correct
30 Correct 526 ms 38692 KB Output is correct
31 Correct 506 ms 36664 KB Output is correct
32 Correct 500 ms 35664 KB Output is correct
33 Correct 524 ms 39336 KB Output is correct
34 Correct 512 ms 36348 KB Output is correct
35 Correct 570 ms 39672 KB Output is correct
36 Correct 128 ms 20828 KB Output is correct
37 Correct 559 ms 39264 KB Output is correct
38 Correct 427 ms 35892 KB Output is correct
39 Correct 244 ms 24912 KB Output is correct
40 Correct 215 ms 24412 KB Output is correct
41 Correct 296 ms 17224 KB Output is correct
42 Correct 185 ms 16292 KB Output is correct
43 Correct 195 ms 16384 KB Output is correct
44 Correct 180 ms 15884 KB Output is correct
45 Correct 234 ms 16144 KB Output is correct
46 Correct 180 ms 15856 KB Output is correct
47 Correct 203 ms 16076 KB Output is correct
48 Correct 191 ms 15548 KB Output is correct
49 Correct 233 ms 16356 KB Output is correct
50 Correct 168 ms 15680 KB Output is correct
51 Correct 134 ms 15516 KB Output is correct
52 Correct 164 ms 15588 KB Output is correct
53 Correct 179 ms 15500 KB Output is correct
54 Correct 139 ms 15944 KB Output is correct
55 Correct 149 ms 15260 KB Output is correct
56 Correct 53 ms 12704 KB Output is correct
57 Correct 141 ms 14796 KB Output is correct
58 Correct 132 ms 14872 KB Output is correct
59 Correct 3 ms 4948 KB Output is correct
60 Correct 3 ms 4948 KB Output is correct
61 Correct 1752 ms 47016 KB Output is correct
62 Correct 1482 ms 44820 KB Output is correct
63 Correct 1471 ms 44084 KB Output is correct
64 Correct 1469 ms 43924 KB Output is correct
65 Correct 1559 ms 44848 KB Output is correct
66 Correct 1516 ms 43228 KB Output is correct
67 Correct 1349 ms 43152 KB Output is correct
68 Correct 1387 ms 41536 KB Output is correct
69 Correct 1384 ms 43984 KB Output is correct
70 Correct 1232 ms 40624 KB Output is correct
71 Correct 1141 ms 42392 KB Output is correct
72 Correct 1193 ms 40640 KB Output is correct
73 Correct 1222 ms 41868 KB Output is correct
74 Correct 1273 ms 43436 KB Output is correct
75 Correct 1221 ms 41716 KB Output is correct
76 Correct 129 ms 20452 KB Output is correct
77 Correct 1099 ms 38864 KB Output is correct
78 Correct 1028 ms 38876 KB Output is correct
79 Correct 3 ms 4948 KB Output is correct
80 Correct 3 ms 5036 KB Output is correct