Submission #1245840

#TimeUsernameProblemLanguageResultExecution timeMemory
1245840kppTeams (CEOI11_tea)C++20
0 / 100
460 ms47992 KiB
#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);
		}
	}
	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]);
      |                 ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...