Submission #829449

#	Time	Username	Problem	Language	Result	Execution time	Memory
829449		rainboy	Inspections (NOI23_inspections)	C11	100 / 100	357 ms	36572 KiB

Main

#include <stdio.h>

#define N	200000
#define M	200000
#define Q	200000
#define M_	(M * 3 + 2)
#define INF	0x3f3f3f3f3f3f3f3fLL

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int zz[M_], ll[M_], rr[M_], ii[M_], jj[M_], u_, l_, r_; long long xx[M_];

int node(int l, int r, long long x) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = l, jj[_] = r, xx[_] = x;
	return _++;
}

void split_i(int u, int i) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (ii[u] <= i) {
		split_i(rr[u], i);
		rr[u] = l_, l_ = u;
	} else {
		split_i(ll[u], i);
		ll[u] = r_, r_ = u;
	}
}

void split_j(int u, int i) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (jj[u] <= i) {
		split_j(rr[u], i);
		rr[u] = l_, l_ = u;
	} else {
		split_j(ll[u], i);
		ll[u] = r_, r_ = u;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

long long tt[M_]; int ww[M_], m_;

void add_segments(int u, int i, int j, long long x) {
	if (u == 0)
		return;
	add_segments(ll[u], i, j, x);
	tt[m_] = xx[u] == -INF ? 0 : x - xx[u], ww[m_] = max(min(j, jj[u]) - max(i, ii[u]) + 1, 0), m_++;
	add_segments(rr[u], i, j, x);
}

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (tt[hh[j]] == tt[h])
				j++;
			else if (tt[hh[j]] < tt[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int main() {
	static int hh[M_];
	static long long kk[M_ + 1];
	int n, m, q, h, i, j;
	long long k;

	scanf("%d%d%d", &n, &m, &q);
	k = 0, u_ = node(0, n - 1, -INF);
	while (m--) {
		int l, m, m_, r, u;

		scanf("%d%d", &i, &j), i--, j--;
		split_j(u_, i - 1), l = l_;
		split_i(r_, j), m = l_, r = r_;
		add_segments(m, i, j, k - i);
		m_ = node(i, j, k - i);
		if (ii[u = first(m)] < i)
			m_ = merge(node(ii[u], i - 1, xx[u]), m_);
		if (jj[u = last(m)] > j)
			m_ = merge(m_, node(j + 1, jj[u], xx[u]));
		u_ = merge(merge(l, m_), r);
		k += j - i + 1;
	}
	for (h = 0; h < m_; h++)
		hh[h] = h;
	sort(hh, 0, m_);
	kk[0] = k;
	for (h = 0; h < m_; h++)
		kk[h + 1] = kk[h] - ww[hh[h]];
	while (q--) {
		long long t;
		int lower, upper;

		scanf("%lld", &t);
		lower = -1, upper = m_;
		while (upper - lower > 1) {
			h = (lower + upper) / 2;
			if (tt[hh[h]] <= t)
				lower = h;
			else
				upper = h;
		}
		printf("%lld ", kk[upper]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:113:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:118:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:140:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   scanf("%lld", &t);
      |   ^~~~~~~~~~~~~~~~~

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