Submission #17872

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17872	2016-01-12T19:52:13 Z	chrome	Collider (IZhO11_collider)	C++	100 / 100	185 ms	50232 KB

collider

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define foreach(it, S) for (__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define _ ios_base :: sync_with_stdio(false); cin.tie(NULL);

#ifdef inputf
	#define fname ""
#else
	#define fname "" // <- Here
#endif

const double eps = 1e-9;
const int MaxN = int(2e5) + 256;
const int MOD = int(1e9) + 7;

template <typename T> inline T gcd(T a, T b) {
	return b ? gcd (b, a % b) : a;
}

inline bool Palindrome(const string& s) {
	return equal(s.begin(), s.end(), s.rbegin());
}

struct node {
	node *l, *r;
	int cnt, x, y;
	node() {}
	node(int x) : x(x), cnt(1), y(rand()), l(NULL), r(NULL) {}
};

typedef node* pnode;
                          
inline int getCnt(pnode &t) {
	return t ? t -> cnt : 0;
}

inline void upd(pnode &t) {
	if (!t)
		return;
	t -> cnt = getCnt(t -> l) + getCnt(t -> r) + 1;
}

pnode Merge(pnode a, pnode b) {
	if (!a)
		return b;
	if (!b)
		return a;
	if (a -> y > b -> y) {
		a -> r = Merge(a -> r, b);
		upd(a);
		return a;
	} else {
		b -> l = Merge(a, b -> l);
		upd(b);
		return b;
	}	
}

void Split(pnode t, int key, pnode &a, pnode &b) {
	if (!t)
		return void(a = b = NULL);
	int cur = getCnt(t -> l) + 1;
	if (cur < key) {
		Split(t -> r, key - cur, t -> r, b);
		a = t;
	} else {
		Split(t -> l, key, a, t -> l);
		b = t;
	}
	upd(a); upd(b);
}

int val[256];
char rvl[4];

void print(pnode t) {
	if (!t)
		return;
	print(t -> l);
	cerr << rvl[t -> x] << " ";
	print(t -> r);
}

inline void Replace(pnode &t, int a, int b) {
	if (a < b) {
		pnode L, R, M1, M2, M3;
		Split(t, a, L, M1);
		Split(M1, 2, M1, M2);
		Split(M2, b - a + 1, M2, R);
		// cerr << a << " " << b << "\n";
		// cerr << "L: "; print(L); cerr << endl; 
		// cerr << "M1: "; print(M1); cerr << endl; 
		// cerr << "M2: "; print(M2); cerr << endl; 
		// cerr << "R: "; print(R); cerr << endl; 
		t = Merge(L, Merge(M2, Merge(M1, R)));
	} else {
		// cerr << "~"; print(t); cerr << endl;
		pnode L, R, M1, M2, M3;
		Split(t, a, L, R);
		Split(R, 2, M1, R);
		Split(L, b, L, M2);
		// cerr << a << " " << b << "\n";
		// cerr << "L: "; print(L); cerr << endl; 
		// cerr << "M1: "; print(M1); cerr << endl; 
		// cerr << "M2: "; print(M2); cerr << endl; 
		// cerr << "R: "; print(R); cerr << endl; 
		t = Merge(L, Merge(M1, Merge(M2, R)));
	}
}

inline char get(pnode &t, int i) {
	pnode L, M, R;
	Split(t, i, L, R);
	Split(R, 2, M, R);
	int val = M -> x;
	t = Merge(L, Merge(M, R));
	return rvl[val];
}

int main() { _
	#ifdef lcl
		freopen(fname".in", "r", stdin);
		freopen(fname".out", "w", stdout);
	#endif

	int n, m; cin >> n >> m;

	pnode t = NULL;
	
	val['x'] = 1; val['y'] = 2; val['z'] = 3;
	rvl[1] = 'x'; rvl[2] = 'y'; rvl[3] = 'z';
	
	string s; cin >> s;
	for (int i = 0; i < n; ++i)
		t = Merge(t, new node(val[s[i]]));

	for (int i = 0; i < m; ++i) {
		char op; cin >> op;
		if (op == 'a') {
			int a, b; cin >> a >> b;
			Replace(t, a, b);
		} else {
			int x; cin >> x;
			cout << get(t, x) << endl;
		}
		// print(t); cerr << endl;
	}

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1716 KB	Output is correct
2	Correct	10 ms	1848 KB	Output is correct
3	Correct	27 ms	6648 KB	Output is correct
4	Correct	142 ms	40860 KB	Output is correct
5	Correct	149 ms	40860 KB	Output is correct
6	Correct	185 ms	45480 KB	Output is correct
7	Correct	181 ms	50232 KB	Output is correct
8	Correct	164 ms	50232 KB	Output is correct
9	Correct	184 ms	50232 KB	Output is correct
10	Correct	172 ms	50232 KB	Output is correct