Submission #1245951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245951		kpp	Teams (CEOI11_tea)	C++20	70 / 100	2597 ms	70704 KiB

tea

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node{int val, lazy, ptr, lptr;};
struct Seg{
	int N;
	vector<Node> t;
	Seg(int n): N(n), t(4*n+4, {0,0,0,-1}) {}
	void prop(int nd, int st, int ed){
		if(t[nd].lazy == 0) return;
		if(t[nd].val < t[nd].lazy){
			t[nd].val = t[nd].lazy;
			t[nd].ptr = t[nd].lptr;
		}
		if(st != ed){
			int L = nd<<1, R = L|1;
			if(t[L].lazy < t[nd].lazy){
				t[L].lazy = t[nd].lazy;
				t[L].lptr = t[nd].lptr;
			}
			if(t[R].lazy < t[nd].lazy){
				t[R].lazy = t[nd].lazy;
				t[R].lptr = t[nd].lptr;
			}
		}
		t[nd].lazy = 0;
		t[nd].lptr = -1;
	}

	void upd(int l, int r, int x, int p){
		struct F{int nd, st, ed, l, r, x, p, stage, md;};
		vector<F> stk;
		stk.reserve(80);
		stk.push_back({1, 1, N, l, r, x, p, 0, 0});
		while(!stk.empty()){
			auto &f = stk.back();
			if(f.stage==0){
				prop(f.nd, f.st, f.ed);
				if(f.r< f.st || f.ed < f.l){
					stk.pop_back();
					continue;
				}
				if(f.l <= f.st && f.ed <= f.r){
					if(t[f.nd].lazy < f.x){
						t[f.nd].lazy = f.x;
						t[f.nd].lptr = f.p;
					}
					prop(f.nd, f.st, f.ed);
					stk.pop_back();
				}
				else{
					f.md = (f.st+f.ed)>>1;
					f.stage = 1;
					stk.push_back({f.nd*2+1, f.md+1, f.ed, f.l, f.r, f.x, f.p, 0, 0});
					stk.push_back({f.nd*2, f.st, f.md, f.l, f.r, f.x, f.p, 0, 0});
				}
			}
			else{
				stk.pop_back();
			}
		}
	}
	int gt(int l, int r){
		struct F{int nd, st, ed, l, r, stage, md;};
		vector<F> stk;
		stk.reserve(80);
		stk.push_back({1, 1, N, l, r, 0, 0});
		int res = 0;
		while(!stk.empty()){
			auto &f = stk.back();
			if(f.stage == 0){
				prop(f.nd, f.st, f.ed);
				if(f.r < f.st || f.ed < f.l){
					stk.pop_back();
					continue;
				}
				if(f.l <= f.st && f.ed <= f.r){
					res = max(res, t[f.nd].val);
					stk.pop_back();
				}
				else{
					f.md = (f.st+f.ed)>>1;
					f.stage = 1;
					stk.push_back({f.nd*2+1, f.md+1, f.ed, f.l, f.r, 0, 0});
					stk.push_back({f.nd*2, f.st, f.md, f.l, f.r, 0, 0});
				}
			}
			else{
				stk.pop_back();
			}
		}
		return res;
	}
	int gp(int p){
		struct F{int nd, st, ed, p;};
		vector<F> stk;
		stk.reserve(80);
		stk.push_back({1, 1, N, p});
		int ans = 0;
		while(!stk.empty()){
			auto f = stk.back(); stk.pop_back();
			prop(f.nd, f.st, f.ed);
			if(f.st == f.ed){
				ans = t[f.nd].ptr;
			}
			else{
				int md = (f.st+f.ed)>>1;
				if(f.p <= md) stk.push_back({f.nd*2, f.st, md, f.p});
				else stk.push_back({f.nd*2+1, md+1, f.ed, f.p});
			}
		}
		return ans;
	}
};

int n;
array<int, 2> a[1000006];

int main(){
	int n;
	scanf("%d", &n);
	for(int i=2; i<=n+1; i++){
		scanf("%d", &a[i][0]);
		a[i][1] = i-1;
	}
	sort(a+2, a+n+2, greater<>());
	Seg seg(n+1);
	seg.upd(1, 1, 1, 1);
	for(int i=2; i<=n+1; i++){
		int L = i+a[i][0]-1;
		int R = n+1;
		int pre = seg.gt(i-1, i-1);
		if(pre > 0) seg.upd(L, R, pre+1, i);
	}
	int res = seg.gt(n+1, n+1)-1;
	int tp = n;
	int sum = 0;
	int cnt = 0;
	while(tp > 1){
		int l = seg.gp(tp);
		if(l-1 <= 2) break;
		if(tp-l+1 >= a[2][0]){
			sum += tp-l+1;
			cnt++;
		}
		tp = l-1;
	}
	int l = a[2][0]-1, r = max(cnt ? sum/cnt : 1, (tp-1)), gap = 1;
	while(l <= r){
		int md = (l+r)/2;
		fill(seg.t.begin(), seg.t.end(), Node{0, 0, 0, -1});
		seg.upd(1, 1, 1, 1);
		for(int i=2; i<=n+1; i++){
			int L = i+a[i][0]-1;
			int R = min(i+md, n+1);
			int pre = seg.gt(i-1, i-1);
			if(pre > 0) seg.upd(L, R, pre+1, i);
		}
		if(seg.gt(n+1, n+1)-1 == res){
			gap = md;
			r = md-1;
		}
		else{
			l = md+1;
		}
	}
	fill(seg.t.begin(), seg.t.end(), Node{0, 0, 0, -1});
	seg.upd(1, 1, 1, 1);
	for(int i=2; i<=n+1; i++){
		int L = i+a[i][0]-1;
		int R = min(i+gap, n+1);
		int pre = seg.gt(i-1, i-1);
		if(pre > 0) seg.upd(L, R, pre+1, i);
	}
	printf("%d\n", res);
	int cp = n+1;
	while(cp > 1){
		int l = seg.gp(cp);
		printf("%d", cp-l+1);
		for(int i=l; i<=cp; i++){
			printf(" %d", a[i][1]);
		}
		cp = l-1;
		printf("\n");
	}
}

Compilation message (stderr)

tea.cpp: In function 'int main()':
tea.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
tea.cpp:124:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |                 scanf("%d", &a[i][0]);
      |                 ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10