Submission #1122853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122853		sleepntsheep	Inspections (NOI23_inspections)	C11	0 / 100	1 ms	324 KiB

Main

#include <stdio.h>

#define N 500005

int n, m, q, pa[N], ch[N][2], rev[N], jj = 200086, last, rt;
long long fresh[N], ss, ans[N], ans2[N];

void pus(int v) { if (rev[v]) { int t = ch[v][0]; ch[v][0] = ch[v][1]; ch[v][1] = t; rev[ch[v][0]] ^= 1; rev[ch[v][1]] ^= 1; rev[v] = 0; } }
void pul(int v) { if(!v) return; ans2[v] = ans2[ch[v][0]] + ans2[ch[v][1]] + ans[v]; }
int isroot(int v) { return ch[pa[v]][0] != v && ch[pa[v]][1] != v; }
void rot(int v) {
	int p = pa[v], g = pa[p], d = ch[p][0] == v;
	if (!isroot(p))
		ch[g][ch[g][1] == p] = v;
	ch[p][!d] = ch[v][d];
	if (ch[v][d]) pa[ch[v][d]] = p;
	pa[pa[ch[v][d] = p] = v] = g;
	pul(p), pul(v);
}
void u____(int v) { if (!isroot(v)) u____(pa[v]); pus(v); }
void splay(int v) {
	u____(v);
	for (int p, g; !isroot(v); rot(v)) if (g = pa[p = pa[v]], !isroot(p)) rot((ch[g][0] == p) == (ch[p][0] == v) ? p : v);
	pul(v);
}
void access(int v) { for (int w = 0; v; v = pa[w = v]) splay(v), ch[v][1] = w, pul(v); }
void makeroot(int v) { access(v), splay(v), rev[v] ^= 1; }
int findroot(int v) {
	access(v), splay(v);
	int r = v;
	while (ch[r][0]) r = ch[r][0];
	return r;
}
int findtail(int v) {
	int r = findroot(v);
	for (int j = 1 << 18; j >>= 1; ) if (v + j <= n && findroot(j + v) == r) v += j;
	return v;
}
void link(int v, int w) { makeroot(v); pa[v] = w; }
void cut(int v) { access(v), splay(v); pa[ch[v][0]] = 0; ch[v][0] = 0; }
int node(long long ke, long long va) { int v = ++jj; fresh[v] = ke; ans2[v] = ans[v] = va; return v; }
void ins(int *rt, int v, int p) {
	if (!*rt) pa[last = *rt = v] = p;
	else if (fresh[*rt] < fresh[v]) ins(ch[*rt] + 1, v, *rt), pul(*rt);
	else if (fresh[*rt] > fresh[v]) ins(ch[*rt], v, *rt), pul(*rt);
	else last = *rt, ans[*rt] += ans[v], pul(*rt);
}
long long cnt(int rt, long long ke) {
	if (!rt) return 0;
	last = rt;
	if (fresh[rt] <= ke) return cnt(ch[rt][1], ke);
	return ans2[ch[rt][1]] + ans[rt] + cnt(ch[rt][0], ke);
}
void cutt(int v) {
	int r = findroot(v);
	fresh[v] = fresh[r] + v - r;
	cut(v);
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	fresh[1] = 1e13;
	for (int i = 2; i <= n; ++i)
		link(i, i - 1);

	for (int l, r; m--; ) {
		scanf("%d%d", &l, &r);
		int y, z, l0 = l;
		cutt(l);
		if (r < n)
			cutt(r + 1);
		for (; l <= r;) {
			y = findroot(l), z = findtail(l);

			long long threshold = ss - fresh[y] - (l - y);
			/* ans[i] += z - l + 1 iff s[i] < threshold */
			ins(&rt, node(threshold, z - l + 1), 0);
			splay(last);
			rt = last;

			if (l0 != y)
				link(y, y - 1);
			l = z + 1;
		}
		fresh[l0] = ss;
		ss += r - l0 + 1;
	}
	
	for (long long s, i = 0; i < q; ++i)
		scanf("%lld\n", &s), printf("%lld ", cnt(rt, s)), splay(last), rt = last;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:60:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d%d%d", &n, &m, &q);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:66:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |                 scanf("%d%d", &l, &r);
      |                 ^~~~~~~~~~~~~~~~~~~~~
Main.c:89:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                 scanf("%lld\n", &s), printf("%lld ", cnt(rt, s)), splay(last), rt = last;
      |                 ^~~~~~~~~~~~~~~~~~~

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