Submission #830909

#	Time	Username	Problem	Language	Result	Execution time	Memory
830909		rainboy	LIS (INOI20_lis)	C11	100 / 100	1503 ms	46476 KiB

Main

#include <stdio.h>

#define N	1000000
#define K	1000000
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(N))) */

unsigned int Z = 12345;

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

int st[N_ * 2], n_;

void build(int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? 1 : 0;
	for (i = n_ - 1; i > 0; i--)
		st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}

void update(int i, int x) {
	for (i += n_; i > 0; i >>= 1)
		st[i] += x;
}

int query(int k) {
	int i = 1;

	while (i < n_)
		if (k < st[i << 1 | 0])
			i = i << 1 | 0;
		else
			k -= st[i << 1 | 0], i = i << 1 | 1;
	return i - n_;
}

int zz[K + 1], ll[K + 1], rr[K + 1], ii[K + 1], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	return _++;
}

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

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 ? ii[u] : first(ll[u]);
}

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

int remove_first(int u) {
	if (ll[u] == 0)
		return rr[u];
	ll[u] = remove_first(ll[u]);
	return u;
}

int aa[N], dp[N], uu[K + 1], k;

void add(int i) {
	int j, l, r;

	while (1) {
		if (dp[i] == k) {
			uu[k++] = node(i);
			return;
		}
		split(uu[dp[i]], i);
		if (l_ && aa[last(l_)] < aa[i])
			uu[dp[i]++] = merge(l_, r_);
		else
			break;
	}
	l = l_, r = r_;
	while (r && aa[i] < aa[j = first(r)]) {
		r = remove_first(r);
		dp[j]++, add(j);
	}
	uu[dp[i]] = merge(merge(l, node(i)), r);
}

int main() {
	static int ii[N], aa_[N];
	int n, h, i;

	scanf("%d", &n);
	for (h = 0; h < n; h++)
		scanf("%d%d", &ii[h], &aa_[h]), ii[h]--;
	build(n);
	for (h = n - 1; h >= 0; h--) {
		i = ii[h] = query(ii[h]);
		aa[i] = aa_[h];
		update(i, -1);
	}
	for (h = 0; h < n; h++) {
		add(ii[h]);
		printf("%d\n", k);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:127:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%d%d", &ii[h], &aa_[h]), ii[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80