oj.uz

Submission #545885

# Submission time Handle Problem Language Result Execution time Memory
545885 2022-04-05T15:53:09 Z rainboy Cake (CEOI14_cake) C
100 / 100
 234 ms 25016 KB 
#include <stdio.h>

#define N	250000
#define Q	500000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define K	10
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }

int st[N_ * 2], n_;

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

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? aa[i] : INF;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

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

int query(int l, int r) {
	int x = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x = max(x, st[l++]);
		if ((r & 1) == 0)
			x = max(x, st[r--]);
	}
	return x;
}

int queryr(int l, int a) {
	int r = n_ - 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st[l] > a) {
				while (l < n_)
					l = st[l << 1 | 0] > a ? l << 1 | 0 : l << 1 | 1;
				return l -= n_;
			}
			l++;
		}
	return n_;
}

int queryl(int r, int a) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st[r] > a) {
				while (r < n_)
					r = st[r << 1 | 1] > a ? r << 1 | 1 : r << 1 | 0;
				return r -= n_;
			}
			r--;
		}
	return -1;
}

int main() {
	static int idx[N], hh[K], aa[N + Q], tt[N + Q], ii[N + Q], prev[N + Q], next[N + Q];
	int n, q, g, g_, h, i, i_, a;

	scanf("%d%d", &n, &i_), i_--;
	for (i = 0; i < n; i++) {
		scanf("%d", &a), a--;
		idx[a] = i;
	}
	for (a = 0; a < n; a++)
		prev[idx[a]] = a == 0 ? -1 : idx[a - 1], next[idx[a]] = a + 1 == n ? -1 : idx[a + 1];
	for (g = 0; g < K; g++)
		hh[g] = n - 1 - g >= 0 ? idx[n - 1 - g] : -1;
	scanf("%d", &q);
	for (i = 0; i < n; i++)
		ii[i] = i;
	for (h = 0; h < q; h++) {
		static char s[2];

		scanf("%s%d", s, &ii[n + h]), ii[n + h]--;
		tt[h] = s[0] == 'F';
		if (s[0] == 'E') {
			scanf("%d", &g), g--;
			prev[n + h] = hh[g], next[n + h] = next[hh[g]], next[hh[g]] = n + h;
			g_ = g;
			while (g_ < K - 1 && ii[hh[g_]] != ii[n + h])
				g_++;
			while (g_ > g)
				hh[g_] = hh[g_ - 1], g_--;
			hh[g] = n + h;
		}
	}
	for (i = 0; i < n + q; i++)
		if (prev[i] == -1) {
			a = 0;
			while (i != -1)
				aa[i] = a++, i = next[i];
			break;
		}
	build(aa, n);
	for (h = 0; h < q; h++)
		if (tt[h] == 0) {
			update(ii[n + h], aa[n + h]);
		} else {
			i = ii[n + h];
			if (i == i_)
				printf("0\n");
			else if (i < i_)
				printf("%d\n", queryr(i_ + 1, query(i, i_ - 1)) - i - 1);
			else
				printf("%d\n", i - queryl(i_ - 1, query(i_ + 1, i)) - 1);
		}
	return 0;
}

Compilation message

cake.c: In function 'main':
cake.c:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%d", &n, &i_), i_--;
      |  ^~~~~~~~~~~~~~~~~~~~~~
cake.c:83:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d", &a), a--;
      |   ^~~~~~~~~~~~~~~
cake.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
cake.c:96:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%s%d", s, &ii[n + h]), ii[n + h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.c:99:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |    scanf("%d", &g), g--;
      |    ^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 5 ms 980 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14788 KB Output is correct
2 Correct 163 ms 14752 KB Output is correct
3 Correct 159 ms 14860 KB Output is correct
4 Correct 149 ms 14868 KB Output is correct
5 Correct 175 ms 15560 KB Output is correct
6 Correct 155 ms 15840 KB Output is correct
7 Correct 170 ms 15696 KB Output is correct
8 Correct 168 ms 15748 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6696 KB Output is correct
2 Correct 46 ms 6500 KB Output is correct
3 Correct 67 ms 6448 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 96 ms 11600 KB Output is correct
6 Correct 91 ms 11728 KB Output is correct
7 Correct 66 ms 11604 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1876 KB Output is correct
2 Correct 16 ms 2004 KB Output is correct
3 Correct 33 ms 4320 KB Output is correct
4 Correct 32 ms 4360 KB Output is correct
5 Correct 44 ms 4684 KB Output is correct
6 Correct 56 ms 7648 KB Output is correct
7 Correct 61 ms 6612 KB Output is correct
8 Correct 70 ms 9732 KB Output is correct
9 Correct 234 ms 24872 KB Output is correct
10 Correct 149 ms 14888 KB Output is correct
11 Correct 175 ms 16332 KB Output is correct
12 Correct 230 ms 23496 KB Output is correct
13 Correct 216 ms 25016 KB Output is correct