제출 #1122846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122846		sleepntsheep	Inspections (NOI23_inspections)	C11	0 / 100	0 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 dfs(int v) {
	if(!v)return;
	dfs(ch[v][0]);
	printf(" (%lld %lld===\n",fresh[v],ans[v]);
	dfs(ch[v][1]);
}

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;
		for (; l <= r;) {
			y = findroot(l), z = findtail(l);
			if (z > r) {
				cut(r + 1);
				fresh[r + 1] = fresh[y] + (r + 1 - y);
				z = r;
			}

			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;

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

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

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

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