Submission #1245950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245950		kpp	Teams (CEOI11_tea)	C++20	80 / 100	2598 ms	77776 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 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<>());
	// for(int i=2; i<=n; i++){
	// 	printf("%d ", a[i][0]);
	// }printf("\n");
	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 tp = n;
	int sum = 0;
	int cnt = 0;
	while(tp > 1){
		int l = seg.gp(1, 1, n, 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;
		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+md, 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);
			}
		}
		if(seg.gt(1, 1, n, n, n)-1 == res){
			gap = md;
			r = md-1;
		}
		else{
			l = md+1;
		}
		// printf("%d %d %d %d %d<\n", l, r, md, seg.gt(1,1,n,n,n), gap);
	}
	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);
		}
	}
	printf("%d\n", seg.gt(1, 1, n, n, n)-1);
	int cp = n;
	while(cp > 1){
		int l = seg.gp(1, 1, n, cp);
		// printf("[%d %d]\n", l, 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:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
tea.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 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: 10 / 10