Submission #396387

#	Time	Username	Problem	Language	Result	Execution time	Memory
396387		srvlt	Collider (IZhO11_collider)	C++17	100 / 100	238 ms	48964 KiB

collider

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) begin(x),end(x)
#define ld long double
#define SZ(x) (int)(x).size()
#define mem(x,y) memset(&x,y,sizeof(x))
#define np nullptr
using namespace std;

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
uniform_int_distribution<int> _p(0,(int)1e9);
namespace treap {
	struct Node {
		int p,sz=1;
		char c;
		Node *l=np,*r=np;
		Node() {}
		Node(char _c) { c=_c,p=_p(rng); }
	};
	typedef Node* node;
	int sz(node v) { return v?v->sz:0; }
	void upd(node v) {
		if(!v) return;
		v->sz=sz(v->l)+sz(v->r)+1;
	}
	node merge(node l,node r){
		if(!l) return r;
		if(!r) return l;
		if(l->p < r->p) {
			r->l=merge(l,r->l);
			upd(r);
			return r;
		}
		l->r=merge(l->r,r);
		upd(l);
		return l;
	}
	array<node,2> split(node t,int k) {
		//first k elements and the rest
		if(!t) return {np,np};
		array<node,2> res;
		if(k<sz(t->l)+1) {
			res=split(t->l,k);
			t->l=res[1];
			upd(t);
			return {res[0],t};
		}
		res=split(t->r,k-sz(t->l)-1);
		t->r=res[0];
		upd(t);
		return {t,res[1]};
	}
	void insert(node &t,node v,int k) {
		//insert just after k-th
		if(!t) t=v;
		else if(t->p < v->p) {
			array<node,2> res=split(t,k);
			v->l=res[0],v->r=res[1];
			t=v;
		}	else {
			if(k<sz(t->l)+1)
				insert(t->l,v,k);
			else
				insert(t->r,v,k-sz(t->l)-1);
		}
		upd(t);
	}
	char erase(node &t,int k) {
		char c;
		if(k==sz(t->l)+1) {
			c=t->c;
			t=merge(t->l,t->r);
		}	else if(k<sz(t->l)+1)
			c=erase(t->l,k);
		else
			c=erase(t->r,k-sz(t->l)-1);
		upd(t);
		return c;
	}
	node find(node &t,int k) {
		if(k==sz(t->l)+1) return t;
		if(k<sz(t->l)+1) return find(t->l,k);
		return find(t->r,k-sz(t->l)-1);
	}
};
using namespace treap;
const int n0=1e6+123;
int n,m;

int main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> n >> m;
	node root=np;
	for(int i=1; i<=n; i++) {
		char c;cin >> c;
		root=merge(root,new Node(c));
	}
	while(m--) {
		char tp;cin >> tp;if(tp=='a') {
			int x,y;cin >> x >> y;
			char c=erase(root,x);
			insert(root,new Node(c),y-1);
		}	else {
			int x;cin >> x;
			cout << find(root,x)->c << '\n';
		}
	}
}

• Subtask 1: 100 / 100