제출 #1122840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122840		sleepntsheep	Inspections (NOI23_inspections)	C11	11 / 100	227 ms	8988 KiB

Main

#include <stdio.h>

#define N 500005

int n, m, q, pa[N], ch[N][2], rev[N], jj = 200086, last;
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 << 19; 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 rt;
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) {
	if (!*rt) { *rt = v; return; }
	if (fresh[*rt] < fresh[v]) ins(ch[*rt] + 1, v), pul(*rt);
	else if (fresh[*rt] > fresh[v]) ins(ch[*rt], v), pul(*rt);
	else 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);
}


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, i = 0; i < m; ++i) {
		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 */
			int kk = node(threshold, z - l + 1);
			ins(&rt, kk);
			splay(kk);			
			
			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:71:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d%d%d", &n, &m, &q);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:77:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |                 scanf("%d%d", &l, &r);
      |                 ^~~~~~~~~~~~~~~~~~~~~
Main.c:101:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 scanf("%lld\n", &s), printf("%lld ", cnt(rt, s)), splay(last);
      |                 ^~~~~~~~~~~~~~~~~~~

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