Submission #1122903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122903		sleepntsheep	Inspections (NOI23_inspections)	C++20	0 / 100	2 ms	580 KiB

Main

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

#define M 30000000

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 (!A[v]) return -1;
	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 (int y; xk; xk--)
		if ((y = prev_(xx[xk], ll[xk], rr[xk])) != -1)
			return y;
	return -1;
}
long long next_(int v, long long l, long long r) {
	if (!A[v]) return -1;
	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 y, j = 0; ++j <= xk;)
		if ((y = next_(xx[j], ll[j], rr[j])) != -1)
			return y;
	return -1;
}

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);
		if (r < n) cut(r + 1);
		for (; l <= r;) {
			z = next(aa, 0, n + 1, l);

			long long threshold = ss + (l - l0) - val[l];
			/* val[i] += z - l iff s[i] < threshold */
			if (threshold >= 0)
				add(bb, 0, 1e18, threshold, z - l);

			if (l0 != l)
				to_link[++k] = l;
			l = z + 1;
		}
		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\n", &s), printf("%lld ", sum(bb, 0, 1e18, s + 1, 1e18));
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d%d", &n, &m, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |                 scanf("%d%d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 scanf("%lld\n", &s), printf("%lld ", sum(bb, 0, 1e18, s + 1, 1e18));
      |                 ~~~~~^~~~~~~~~~~~~~

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