Submission #703057

#	Time	Username	Problem	Language	Result	Execution time	Memory
703057		rainboy	Collider (IZhO11_collider)	C11	100 / 100	192 ms	19260 KiB

collider

#include <stdio.h>

#define N	1000000
#define Q	15000
#define N_	(N + Q + 1)

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int zz[N_], ll[N_], rr[N_], kk[N_], u_, l_, r_; char cc_[N_];

int node(char c) {
	static int _ = 1;

	zz[_] = rand_();
	kk[_] = 1;
	cc_[_] = c;
	return _++;
}

void pul(int u) {
	kk[u] = kk[ll[u]] + kk[rr[u]] + 1;
}

void split(int u, int k) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (kk[ll[u]] < k) {
		split(rr[u], k - kk[ll[u]] - 1);
		rr[u] = l_, l_ = u;
	} else {
		split(ll[u], k);
		ll[u] = r_, r_ = u;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int remove_first(int u) {
	if (ll[u] == 0)
		return rr[u];
	ll[u] = remove_first(ll[u]), pul(u);
	return u;
}

int main() {
	static char cc[N + 1];
	int n, m, i, j;

	scanf("%d%d%s", &n, &m, cc);
	for (i = 0; i < n; i++)
		u_ = merge(u_, node(cc[i]));
	while (m--) {
		static char s[2];
		char c;

		scanf("%s", s);
		if (s[0] == 'a') {
			scanf("%d%d", &i, &j), i--, j--;
			split(u_, i);
			c = cc_[first(r_)];
			u_ = merge(l_, remove_first(r_));
			split(u_, j);
			u_ = merge(merge(l_, node(c)), r_);
		} else {
			scanf("%d", &i), i--;
			split(u_, i);
			printf("%c\n", cc_[first(r_)]);
			u_ = merge(l_, r_);
		}
	}
	return 0;
}

Compilation message (stderr)

collider.c: In function 'main':
collider.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d%s", &n, &m, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
collider.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
collider.c:81:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
collider.c:88:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100