oj.uz

Submission #264326

# Submission time Handle Problem Language Result Execution time Memory
264326 2020-08-14T06:12:13 Z 송준혁(#5083) Teams (CEOI11_tea) C++17
100 / 100
 564 ms 88952 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N;
pii A[1010101];
int D[1010101], P[1010101];
pii T[1010101];
vector<pii> V[1010101];

void upd(int k, pii v){while (k<=N){T[k]=max(T[k],v), k+=k&-k;}}
pii read(int k){pii r(0,0); while (k){r=max(T[k],r), k^=k&-k;} return r;}

int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%d", &A[i].fi), A[i].se=i;
	sort(A+1, A+N+1);
	for (int i=1; i<=N; i++){
		for (pii t : V[i]) upd(t.se, t);
		if (i-A[i].fi<0) continue;
		pii x = read(i-A[i].fi);
		D[i] = x.fi+1, P[i] = x.se;
		if (2*i-x.se <= N) V[2*i-x.se].pb(pii(D[i], i));
	}
	printf("%d\n", D[N]);
	int t=N;
	while (t){
		printf("%d ", t-P[t]);
		for (int i=P[t]+1; i<=t; i++) printf("%d ", A[i].se);
		printf("\n");
		t = P[t];
	}
	return 0;
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
tea.cpp:20:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  for (int i=1; i<=N; i++) scanf("%d", &A[i].fi), A[i].se=i;
      |                           ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24064 KB Output is correct
2 Correct 18 ms 24064 KB Output is correct
3 Correct 16 ms 24064 KB Output is correct
4 Correct 19 ms 24064 KB Output is correct
5 Correct 16 ms 24064 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 18 ms 24064 KB Output is correct
3 Correct 17 ms 24064 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 16 ms 24064 KB Output is correct
3 Correct 19 ms 24064 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24320 KB Output is correct
2 Correct 18 ms 24320 KB Output is correct
3 Correct 18 ms 24320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24320 KB Output is correct
2 Correct 18 ms 24320 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27128 KB Output is correct
2 Correct 56 ms 29176 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 28280 KB Output is correct
2 Correct 58 ms 28664 KB Output is correct
3 Correct 56 ms 28280 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 69440 KB Output is correct
2 Correct 386 ms 72568 KB Output is correct
3 Correct 390 ms 64760 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 75732 KB Output is correct
2 Correct 559 ms 88952 KB Output is correct
3 Correct 512 ms 85880 KB Output is correct
4 Correct 494 ms 77364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 47092 KB Output is correct
2 Correct 322 ms 38916 KB Output is correct
3 Correct 547 ms 85856 KB Output is correct
4 Correct 564 ms 83460 KB Output is correct