Submission #1245954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245954		kpp	Teams (CEOI11_tea)	C++20	0 / 100	620 ms	85548 KiB

tea

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

/*
	2 1 2 2 3 -> {2, 4}, {1, 3, 5}
	만들 수 있는 최대 팀 크기를 원하는거면, ai정렬해서 큰거부터 보면 안되나?
	3 2 2 2 1 -> [3, 2, 2], [2, 1]
	만약 3 3 3 3 1이라고 하면, [3, 3, 3, 3], [1] 처럼 나눠져야 한다.
	좀 쉽지않네 3 3 3 3 1 1 1 -> [3, 3, 3], [3, 1, 1], [1]보다 [3, 3, 3, 3], [1], [1], [1]이 낫다
	근데 어쨌든 현재 값이 ai라면, [i+ai-1, N]까지의 모든 구간에 대해 group + 1 갱신을 할 수 있는거 아닐까?
	아니근데 n 100만은 좀 크긴하네
	아니근데 역추적을 해야하네네
*/

struct Node{int val, lazy, ptr, lptr;};
struct Seg{
	Node tree[4000006];
	void prop(int nd, int st, int ed){
		if(tree[nd].val < tree[nd].lazy){
			tree[nd].val = tree[nd].lazy;
			tree[nd].ptr = tree[nd].lptr;
		}
		if(st != ed){
			if(tree[nd*2].lazy < tree[nd].lazy){
				tree[nd*2].lazy = tree[nd].lazy;
				tree[nd*2].lptr = tree[nd].lptr;
			}
			if(tree[nd*2+1].lazy < tree[nd].lazy){
				tree[nd*2+1].lazy = tree[nd].lazy;
				tree[nd*2+1].lptr = tree[nd].lptr;
			}
		}
		tree[nd].lazy = 0;
		tree[nd].lptr = -1;
	}
	void upd(int nd, int st, int ed, int l, int r, int x, int ptr){
		prop(nd, st, ed);
		if(r < st || ed < l) return;
		if(l <= st && ed <= r){
			if(tree[nd].lazy < x){
				tree[nd].lazy = x;
				tree[nd].lptr = ptr;
			}
			prop(nd, st, ed);
			return;
		}
		int md = (st+ed)/2;
		upd(nd*2, st, md, l, r, x, ptr);
		upd(nd*2+1, md+1, ed, l, r, x, ptr);
	}
	int gt(int nd, int st, int ed, int l, int r){
		prop(nd, st, ed);
		if(r < st || ed < l) return 0;
		if(l <= st && ed <= r){
			return tree[nd].val;
		}
		int md = (st+ed)/2;
		return max(gt(nd*2, st, md, l, r), gt(nd*2+1, md+1, ed, l, r));
	}
	int gp(int nd, int st, int ed, int p){
		prop(nd, st, ed);
		if(st == ed){
			return tree[nd].ptr;
		}
		int md = (st+ed)/2;
		if(p <= md) return gp(nd*2, st, md, p);
		else return gp(nd*2+1, md+1, ed, p);
	}
}seg;

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

int cal(int x){
	tot[1] = 0;
	last[1] = 0;
	for(int i=2; i<=n; i++){
		int hi = i-a[i][0];
		int lo = i-x;
		if(hi < 0){
			tot[i] = -1e9;
		}
		else{
			int j = last[hi];
			if(j >= lo){
				tot[i] = tot[j]+1;
			}
			else{
				tot[i] = -1e9;
			}
		}
		if(tot[i] >= 0) last[i] = i;
		else last[i] = last[i-1];
	}
	return tot[n];
}

int main(){
	scanf("%d", &n);
	n++;
	for(int i=2; i<=n; i++){
		scanf("%d", &a[i][0]);
		a[i][1] = i-1;
	}
	sort(a+2, a+n+1, greater<>());
	seg.upd(1, 1, n, 1, 1, 1, 1);
	for(int i=2; i<=n; i++){
		int l = i+a[i][0]-1;
		int r = n;
		int pre = seg.gt(1, 1, n, i-1, i-1);
		if(pre > 0){
			seg.upd(1, 1, n, l, r, pre+1, i);
		}
	}
	int res = seg.gt(1, 1, n, n, n)-1;
	int T = cal(n);
	int l = 1, r = n, gap = n;
	while(l <= r){
		int md = (l+r)/2;
		if(cal(md) == T){
			gap = md;
			r = md-1;
		}
		else{
			l = md+1;
		}
	}
	printf("%d\n", seg.gt(1, 1, n, n, n)-1);
	for(int i=1; i<=4*n; i++){
		seg.tree[i].val = seg.tree[i].lazy = seg.tree[i].lptr = seg.tree[i].ptr = 0;
	}
	seg.upd(1, 1, n, 1, 1, 1, 1);
	for(int i=2; i<=n; i++){
		int l = i+a[i][0]-1;
		int r = min(i+gap, n);
		int pre = seg.gt(1, 1, n, i-1, i-1);
		if(pre > 0){
			seg.upd(1, 1, n, l, r, pre+1, i);
		}
	}
	int cp = n;
	while(cp > 1){
		int l = seg.gp(1, 1, n, 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:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
tea.cpp:105:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 scanf("%d", &a[i][0]);
      |                 ~~~~~^~~~~~~~~~~~~~~~

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