Submission #57548

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
57548	2018-07-15T08:33:06 Z	윤교준(#1672)	Teams (CEOI11_tea)	C++11	100 / 100	1260 ms	209232 KB

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int MAXN = 1000005;
const int MX = 2097152;

struct SEG {
	multiset<int> pd[MX];
	int d[MX*2];

	void init() {
		for(int i = 0; i < MX; i++) pd[i].clear();
		fill(d, d+MX*2, -INF);
	}
	void insert(int x, int r) {
		pd[x].insert(-r);
		d[x+MX] = -(*pd[x].begin());
		for(x = (x+MX)>>1; x; x >>= 1)
			d[x] = max(d[x<<1], d[x<<1 | 1]);
	}
	void remove(int x, int r) {
		pd[x].erase(pd[x].find(-r));
		d[x+MX] = pd[x].empty() ? -INF : -(*pd[x].begin());
		for(x = (x+MX)>>1; x; x >>= 1)
			d[x] = max(d[x<<1], d[x<<1 | 1]);
	}
	int get(int s, int e) {
		int r = -INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) upmax(r, d[s++]); if(~e&1) upmax(r, d[e--]);
		} return r;
	}
} seg;

priority_queue<pii, vector<pii>, greater<pii>> PQ;
vector<int> AnsV[MAXN];

int dp[MAXN];

vector<int> BV[MAXN];
int A[MAXN], B[MAXN];

int N, AnsC, AnsL;

int f(int L) {
	seg.init();
	dp[0] = 0; seg.insert(A[1], 0);
	for(int i = 1, j; i <= N; i++) {
		j = i-L-1;
		if(0 <= j) seg.remove(j + A[j+1], dp[j]);
		dp[i] = seg.get(0, i) + 1;
		seg.insert(i + A[i+1], dp[i]);
	}
	return dp[N];
}

int getAnsL() {
	int s = 1, e = N; for(int m; s < e;) {
		m = (s+e)/2;
		if(f(m) != AnsC) s = m+1;
		else e = m;
	}
	return s;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		B[i] = A[i];
	}
	for(int i = 1; i <= N; i++) BV[B[i]].eb(i);
	sort(A+1, A+N+1); reverse(A+1, A+N+1);


	if(300000 <= N) {
		for(int i = 1; i <= N;) {
			if(i+A[i]-1 <= N) {
				AnsC++;
				for(int j = i; j < i+A[i]; j++)
					AnsV[AnsC].eb(A[j]);
				PQ.push(pii(A[i], AnsC));
				i += A[i];
				continue;
			}

			for(int idx, cnt;;) {
				tie(cnt, idx) = PQ.top(); PQ.pop();
				if(sz(AnsV[idx]) != cnt) continue;

				AnsV[idx].eb(A[i]);
				PQ.push(pii(cnt+1, idx));
				break;
			}

			i++;
		}

		printf("%d\n", AnsC);
		for(int i = 1; i <= AnsC; i++) {
			printf("%d ", sz(AnsV[i]));
			for(int v : AnsV[i]) {
				printf("%d ", BV[v].back());
				BV[v].pop_back();
			}
			puts("");
		}
		return 0;
	}


	AnsC = f(INF); AnsL = getAnsL();

	printf("%d\n", f(AnsL));
	for(int i = N, j; i;) {
		for(j = i-1; 0 <= j; j--) {
			if(i < j + A[j+1]) continue;
			if(dp[j]+1 != dp[i]) continue;
			break;
		}
		printf("%d ", i-j);
		for(int k = j+1, v; k <= i; k++) {
			v = A[k];
			printf("%d ", BV[v].back());
			BV[v].pop_back();
		}
		puts("");

		i = j;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	162296 KB	Output is correct
2	Correct	275 ms	162408 KB	Output is correct
3	Correct	284 ms	162500 KB	Output is correct
4	Correct	255 ms	162536 KB	Output is correct
5	Correct	281 ms	162536 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	313 ms	162536 KB	Output is correct
2	Correct	319 ms	162536 KB	Output is correct
3	Correct	369 ms	162536 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	360 ms	162536 KB	Output is correct
2	Correct	383 ms	162560 KB	Output is correct
3	Correct	382 ms	162560 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	432 ms	162868 KB	Output is correct
2	Correct	472 ms	162868 KB	Output is correct
3	Correct	506 ms	162868 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	485 ms	163064 KB	Output is correct
2	Correct	495 ms	163064 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	948 ms	168188 KB	Output is correct
2	Correct	1090 ms	168188 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1260 ms	168872 KB	Output is correct
2	Correct	914 ms	168872 KB	Output is correct
3	Correct	918 ms	168880 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	384 ms	168880 KB	Output is correct
2	Correct	324 ms	168880 KB	Output is correct
3	Correct	353 ms	168880 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	432 ms	173268 KB	Output is correct
2	Correct	528 ms	209232 KB	Output is correct
3	Correct	531 ms	209232 KB	Output is correct
4	Correct	459 ms	209232 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	432 ms	209232 KB	Output is correct
2	Correct	410 ms	209232 KB	Output is correct
3	Correct	482 ms	209232 KB	Output is correct
4	Correct	677 ms	209232 KB	Output is correct

Submission #57548

Compilation message