Submission #543940

#	Time	Username	Problem	Language	Result	Execution time	Memory
543940		rainboy	Radio (COCI22_radio)	C11	110 / 110	826 ms	179184 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	1000000
#define K	7	/* 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 > N */
#define N_	(1 << 24)	/* N_ = pow2(ceil(log2(N))) */
#define Q	200000
#define N1	(2 + Q * K)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

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

int pp[N + 1][K], kk_[N + 1], ll_[N + 2];

void init() {
	int a, b;

	for (a = 2; a <= N; a++) {
		if (kk_[a])
			continue;
		for (b = a; b <= N; b += a)
			pp[b][kk_[b]++] = a;
	}
	for (a = 1; a <= N + 1; a++)
		ll_[a] = ll_[a - 1] + kk_[a - 1];
}

int zz[1 + N1], ll[1 + N1], rr[1 + N1], kk[1 + N1], u_, l_, r_;

int node(int k) {
	static int _ = 1;

	zz[_] = rand_();
	kk[_] = k;
	return _++;
}

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

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);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

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

int st[N_ * 2];

void pul(int i) {
	st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}

void update(int i, int x) {
	st[i += N_] = x;
	while (i > 1)
		pul(i >>= 1);
}

void update_(int i, int p, int x) {
	int h;

	for (h = 0; h < kk_[i]; h++)
		if (pp[i][h] == p) {
			update(ll_[i] + h, x);
			break;
		}
}

int query(int l) {
	int r = N_ - 1, x = INF;

	for (l += N_, r += N_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1)
			x = min(x, st[l++]);
	return x;
}

int main() {
	static char on[N + 1];
	static int tt[N + 1];
	int n, q;

	init();
	scanf("%d%d", &n, &q);
	memset(st, 0x3f, N_ * 2 * sizeof *st);
	while (q--) {
		static char cc[N + 1];
		int h, i, p, l, r;

		scanf("%s", cc);
		if (cc[0] == 'S') {
			scanf("%d", &i);
			if (!on[i]) {
				on[i] = 1;
				for (h = 0; h < kk_[i]; h++) {
					p = pp[i][h];
					split(tt[p], i);
					if (l_)
						update_(kk[last(l_)], p, i);
					if (r_)
						update_(i, p, kk[first(r_)]);
					tt[p] = merge(merge(l_, node(i)), r_);
				}
			} else {
				on[i] = 0;
				for (h = 0; h < kk_[i]; h++) {
					p = pp[i][h];
					split(tt[p], i);
					update_(i, p, INF);
					if (l_)
						update_(kk[last(l_)], p, r_ ? kk[first(r_)] : INF);
					tt[p] = merge(l_, r_);
				}
			}
		} else {
			scanf("%d%d", &l, &r);
			printf(query(ll_[l]) <= r ? "DA\n" : "NE\n");
		}
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:115:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:121:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%s", cc);
      |   ^~~~~~~~~~~~~~~
Main.c:123:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |    scanf("%d", &i);
      |    ^~~~~~~~~~~~~~~
Main.c:147:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |    scanf("%d%d", &l, &r);
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70