제출 #1122915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122915		sleepntsheep	Inspections (NOI23_inspections)	C++20	100 / 100	928 ms	56400 KiB

Main

#include <stdio.h>
#include <stdlib.h>

#define M 120500000

int n, m, q, L[M], R[M], ii, aa, bb, to_link[1 << 19], k;
long long A[M], val[1 << 19], ss;

void add(int &v, long long l, long long r, long long p, long long x) {
	if (!v) v = ++ii;
	A[v] += x;
	if (l == r) return;
	if ((l + r) / 2 >= p) add(L[v], l, (l + r) / 2, p, x);
	else add(R[v], (l + r) / 2 + 1, r, p, x);
}
int xx[80], xk; long long ll[80], rr[80];
void gen(int v, long long l, long long r, long long x, long long y) {
	if (!v || y < l || r < x) return;
	if (x <= l && r <= y) { xx[++xk] = v; ll[xk] = l, rr[xk] = r; return; }
	gen(L[v], l, (l + r) / 2, x, y), gen(R[v], (l + r) / 2 + 1, r, x, y);
}
long long sum(int v, long long l, long long r, long long x, long long y) {
	long long z = 0;
	xk = 0; gen(v, l, r, x, y);
	while (xk) z += A[xx[xk--]];
	return z;
}
long long prev_(int v, long long l, long long r) {
	if (l == r) return l;
	return A[R[v]] ? prev_(R[v], (l + r) / 2 + 1, r) : prev_(L[v], l, (l + r) / 2);
}
long long prev(int v, long long l, long long r, long long x) {
	xk = 0; gen(v, l, r, l, x - 1);
	for (; xk; xk--) if (A[xx[xk]])	return prev_(xx[xk], ll[xk], rr[xk]);
}
long long next_(int v, long long l, long long r) {
	if (l == r) return l;
	return A[L[v]] ? next_(L[v], l, (l + r) / 2) : next_(R[v], (l + r) / 2 + 1, r);
}
long long next(int v, long long l, long long r, long long x) {
	xk = 0; gen(v, l, r, x + 1, r);
	for (int j = 0; ++j <= xk;) if (A[xx[j]]) return next_(xx[j], ll[j], rr[j]);
}

void cut(int v) {
	int r = prev(aa, 0, n + 1, v + 1);
	if (r == v) return;
	val[v] = val[r] + v - r;
	add(aa, 0, n + 1, v, 1);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	val[1] = 1e13;
	add(aa, 0, n + 1, 1, 1);
	add(aa, 0, n + 1, n + 1, 1);
	for (int l, r; m--; ) {
		scanf("%d%d", &l, &r);
		int z, l0 = l;
		cut(l);
		cut(r + 1);
		for (; l <= r; l = z) {
			z = next(aa, 0, n + 1, l);

			long long threshold = ss + (l - l0) - val[l];
			if (threshold >= 0) add(bb, 0, 1e18, threshold, z - l);

			if (l0 != l) to_link[++k] = l;
		}
		while (k) add(aa, 0, n + 1, to_link[k--], -1);
		val[l0] = ss;
		ss += r - l0 + 1;
	}

	for (long long s, i = 0; i < q; ++i)
		scanf("%lld", &s), printf("%lld ", sum(bb, 0, 1e18, s + 1, 1e18));
}

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

Main.cpp: In function 'long long int prev(int, long long int, long long int, long long int)':
Main.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
   35 | }
      | ^
Main.cpp: In function 'long long int next(int, long long int, long long int, long long int)':
Main.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d%d", &n, &m, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 scanf("%d%d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:76:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |                 scanf("%lld", &s), printf("%lld ", sum(bb, 0, 1e18, s + 1, 1e18));
      |                 ~~~~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 23 / 23