제출 #661134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
661134		rainboy	푸드 코트 (JOI21_foodcourt)	C11	100 / 100	358 ms	30568 KiB

foodcourt

#include <stdio.h>
#include <sys/time.h>

#define N	250000
#define M	250000
#define Q	250000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(Q + 1))) */

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

unsigned int X = 12345;

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

int xx[Q * 2], hh[Q * 2];
int tt[Q], ll[Q], rr[Q], ii[Q], cc[Q], ans[Q]; long long kk[Q];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[hh[j]] == xx[h])
				j++;
			else if (xx[hh[j]] < xx[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

long long sta[N_ * 2], stb[N_ * 2], stab[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	sta[i] = sta[l] + sta[r];
	stb[i] = stb[l] + stb[r];
	stab[i] = min(stab[l] + stb[r], sta[l] + stab[r]);
}

void update(int i, long long a, long long b) {
	i += n_;
	sta[i] += a, stb[i] += b, stab[i] = min(sta[i], stb[i]);
	while (i > 1)
		pul(i >>= 1);
}

void query_lr(int r, long long *a_, long long *ab_) {
	int l;
	long long a, b, ab;

	a = 0, b = 0, ab = 0;
	for (l = 0 + n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			ab = min(sta[r] + ab, stab[r] + b), a += sta[r], b += stb[r], r--;
	*a_ = a, *ab_ = ab;
}

int query_i(long long a) {
	int i = 1;

	while (i < n_)
		if (a <= sta[i << 1 | 0])
			i = i << 1 | 0;
		else
			a -= sta[i << 1 | 0], i = i << 1 | 1;
	return i - n_;
}

int main() {
	int n, m, q, h;

	scanf("%d%*d%d", &n, &q);
	for (h = 0; h < q; h++) {
		scanf("%d", &tt[h]);
		if (tt[h] == 1)
			scanf("%d%d%d%lld", &ll[h], &rr[h], &cc[h], &kk[h]), ll[h]--, rr[h]--;
		else if (tt[h] == 2)
			scanf("%d%d%lld", &ll[h], &rr[h], &kk[h]), ll[h]--, rr[h]--;
		else
			scanf("%d%lld", &ii[h], &kk[h]), ii[h]--;
	}
	m = 0;
	for (h = 0; h < q; h++)
		if (tt[h] != 3)
			xx[hh[m++] = h << 1 | 0] = ll[h] * 3 + 0, xx[hh[m++] = h << 1 | 1] = rr[h] * 3 + 2;
		else
			xx[hh[m++] = h << 1 | 0] = ii[h] * 3 + 1;
	sort(hh, 0, m);
	n_ = 1;
	while (n_ <= q)
		n_ <<= 1;
	for (h = 0; h < m; h++) {
		int h_ = hh[h], h1 = h_ >> 1;
		long long l, r;

		if (tt[h1] == 1)
			update(h1, (h_ & 1) == 0 ? kk[h1] : -kk[h1], 0);
		else if (tt[h1] == 2)
			update(h1, 0, (h_ & 1) == 0 ? kk[h1] : -kk[h1]);
		else {
			query_lr(h1, &r, &l);
			if (kk[h1] <= r - l)
				ans[h1] = cc[query_i(l + kk[h1])];
		}
	}
	for (h = 0; h < q; h++)
		if (tt[h] == 3)
			printf("%d\n", ans[h]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.c: In function 'main':
foodcourt.c:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d%*d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.c:83:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~
foodcourt.c:85:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    scanf("%d%d%d%lld", &ll[h], &rr[h], &cc[h], &kk[h]), ll[h]--, rr[h]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.c:87:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |    scanf("%d%d%lld", &ll[h], &rr[h], &kk[h]), ll[h]--, rr[h]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.c:89:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |    scanf("%d%lld", &ii[h], &kk[h]), ii[h]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11