Submission #676549

#	Time	Username	Problem	Language	Result	Execution time	Memory
676549		QwertyPi	Collider (IZhO11_collider)	C++14	100 / 100	264 ms	49936 KiB

collider

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	node *ll, *rr; int prior, cnt, val;
	node(int val, int prior) : val(val), prior(prior), cnt(1), ll(nullptr), rr(nullptr) {};
	node(int val, int prior, node *l, node *r) : val(val), prior(prior), ll(l), rr(r) {};
};

void _crawl(node* t){
	if(!t) return;
	if(t->ll) _crawl(t->ll);
	cout << (char) t->val;
	if(t->rr) _crawl(t->rr);
}

int _count(node* t){
	if(!t) return 0;
	return (t->ll ? t->ll->cnt : 0) + (t->rr ? t->rr->cnt : 0) + 1;
}

int _prior(node* t){
	if(!t) return 0;
	return t->prior;
}

void upd(node*& t){
	if(t) t->cnt = _count(t);
}

void split(node* t, int cnt, node*& l, node*& r){
	if(!t) return void(l = r = nullptr);
	if(cnt >= _count(t->ll) + 1){
		split(t->rr, cnt - _count(t->ll) - 1, t->rr, r); l = t;
	}else{
		split(t->ll, cnt, l, t->ll); r = t;
	}
	upd(l); upd(r);
}

void merge(node*& t, node* l, node* r){
	if(!l || !r) return void(t = l ? l : r);
	if(l->prior >= r->prior) merge(l->rr, l->rr, r), t = l;
	else merge(r->ll, l, r->ll), t = r;
	upd(t);
}

void insert(node*& t, int idx, int val, int prior){
	if(!t) return void(t = new node(val, prior));
	if(prior >= _prior(t)){
		node *x, *y;
		split(t, idx - 1, x, y);
		t = new node(val, prior); t->ll = x; t->rr = y;
	}
	else if(idx <= _count(t->ll) + 1) insert(t->ll, idx, val, prior);
	else insert(t->rr, idx - _count(t->ll) - 1, val, prior); 
	upd(t);
}

void erase(node*& t, int idx){
	node *x, *y, *v;
	split(t, idx - 1, x, y);
	split(y, 1, v, y);
	merge(t, x, y);
	upd(t);
}

int qry(node*& t, int idx){
	if(!t) cout << "WTF" << endl;
	if(_count(t->ll) >= idx) return qry(t->ll, idx);
	else if(idx == _count(t->ll) + 1) return t->val;
	else return qry(t->rr, idx - _count(t->ll) - 1);
}

int main(){
	int n, q; cin >> n >> q;
	string s; cin >> s;
	node* root = nullptr;
	
	for(int i = 1; i <= n; i++){
		insert(root, i, s[i - 1], rng());
	}
	for(int i = 0; i < q; i++){
		char c; int x, y; cin >> c;
		if(c == 'a'){
			cin >> x >> y;
			if(x == y) continue;
			int val = qry(root, x);
			erase(root, x);
			insert(root, y, val, rng());
		}else{
			cin >> x;
			cout << (char) qry(root, x) << endl;
		}
	}
}

Compilation message (stderr)

collider.cpp: In constructor 'node::node(int, int)':
collider.cpp:8:33: warning: 'node::val' will be initialized after [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |                                 ^~~
collider.cpp:8:21: warning:   'int node::prior' [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |                     ^~~~~
collider.cpp:9:2: warning:   when initialized here [-Wreorder]
    9 |  node(int val, int prior) : val(val), prior(prior), cnt(1), ll(nullptr), rr(nullptr) {};
      |  ^~~~
collider.cpp:8:28: warning: 'node::cnt' will be initialized after [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |                            ^~~
collider.cpp:8:8: warning:   'node* node::ll' [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |        ^~
collider.cpp:9:2: warning:   when initialized here [-Wreorder]
    9 |  node(int val, int prior) : val(val), prior(prior), cnt(1), ll(nullptr), rr(nullptr) {};
      |  ^~~~
collider.cpp: In constructor 'node::node(int, int, node*, node*)':
collider.cpp:8:33: warning: 'node::val' will be initialized after [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |                                 ^~~
collider.cpp:8:21: warning:   'int node::prior' [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |                     ^~~~~
collider.cpp:10:2: warning:   when initialized here [-Wreorder]
   10 |  node(int val, int prior, node *l, node *r) : val(val), prior(prior), ll(l), rr(r) {};
      |  ^~~~
collider.cpp:8:21: warning: 'node::prior' will be initialized after [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |                     ^~~~~
collider.cpp:8:8: warning:   'node* node::ll' [-Wreorder]
    8 |  node *ll, *rr; int prior, cnt, val;
      |        ^~
collider.cpp:10:2: warning:   when initialized here [-Wreorder]
   10 |  node(int val, int prior, node *l, node *r) : val(val), prior(prior), ll(l), rr(r) {};
      |  ^~~~

• Subtask 1: 100 / 100