답안 #703057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703057	2023-02-25T20:12:41 Z	rainboy	입자 가속기 (IZhO11_collider)	C	100 / 100	192 ms	19260 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	9 ms	568 KB	Output is correct
3	Correct	23 ms	2288 KB	Output is correct
4	Correct	116 ms	15200 KB	Output is correct
5	Correct	126 ms	15436 KB	Output is correct
6	Correct	153 ms	17416 KB	Output is correct
7	Correct	192 ms	19260 KB	Output is correct
8	Correct	134 ms	19028 KB	Output is correct
9	Correct	181 ms	19260 KB	Output is correct
10	Correct	155 ms	19132 KB	Output is correct