# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
57546 |
2018-07-15T08:30:58 Z |
윤교준(#1672) |
Teams (CEOI11_tea) |
C++11 |
|
2500 ms |
204448 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const int MAXN = 1000005;
const int MX = 2097152;
struct SEG {
multiset<int> pd[MX];
int d[MX*2];
void init() {
for(int i = 0; i < MX; i++) pd[i].clear();
fill(d, d+MX*2, -INF);
}
void insert(int x, int r) {
pd[x].insert(-r);
d[x+MX] = -(*pd[x].begin());
for(x = (x+MX)>>1; x; x >>= 1)
d[x] = max(d[x<<1], d[x<<1 | 1]);
}
void remove(int x, int r) {
pd[x].erase(pd[x].find(-r));
d[x+MX] = pd[x].empty() ? -INF : -(*pd[x].begin());
for(x = (x+MX)>>1; x; x >>= 1)
d[x] = max(d[x<<1], d[x<<1 | 1]);
}
int get(int s, int e) {
int r = -INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
if(s&1) upmax(r, d[s++]); if(~e&1) upmax(r, d[e--]);
} return r;
}
} seg;
int dp[MAXN];
vector<int> BV[MAXN];
int A[MAXN], B[MAXN];
int N, AnsC, AnsL;
int f(int L) {
seg.init();
dp[0] = 0; seg.insert(A[1], 0);
for(int i = 1, j; i <= N; i++) {
j = i-L-1;
if(0 <= j) seg.remove(j + A[j+1], dp[j]);
dp[i] = seg.get(0, i) + 1;
seg.insert(i + A[i+1], dp[i]);
}
return dp[N];
}
int getAnsL() {
int s = 1, e = N; for(int m; s < e;) {
m = (s+e)/2;
if(f(m) != AnsC) s = m+1;
else e = m;
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> A[i];
B[i] = A[i];
}
for(int i = 1; i <= N; i++) BV[B[i]].eb(i);
sort(A+1, A+N+1); reverse(A+1, A+N+1);
AnsC = f(INF); AnsL = getAnsL();
printf("%d\n", f(AnsL));
for(int i = N, j; i;) {
for(j = i-1; 0 <= j; j--) {
if(i < j + A[j+1]) continue;
if(dp[j]+1 != dp[i]) continue;
break;
}
printf("%d ", i-j);
for(int k = j+1, v; k <= i; k++) {
v = A[k];
printf("%d ", BV[v].back());
BV[v].pop_back();
}
puts("");
i = j;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
171 ms |
138780 KB |
Output is correct |
2 |
Correct |
273 ms |
138836 KB |
Output is correct |
3 |
Correct |
288 ms |
138908 KB |
Output is correct |
4 |
Correct |
258 ms |
138908 KB |
Output is correct |
5 |
Correct |
247 ms |
138908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
299 ms |
139056 KB |
Output is correct |
2 |
Correct |
317 ms |
139056 KB |
Output is correct |
3 |
Correct |
323 ms |
139056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
339 ms |
139056 KB |
Output is correct |
2 |
Correct |
333 ms |
139056 KB |
Output is correct |
3 |
Correct |
335 ms |
139056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
439 ms |
139340 KB |
Output is correct |
2 |
Correct |
437 ms |
139368 KB |
Output is correct |
3 |
Correct |
473 ms |
139396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
443 ms |
139408 KB |
Output is correct |
2 |
Correct |
470 ms |
139488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1055 ms |
144644 KB |
Output is correct |
2 |
Correct |
1010 ms |
144856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1048 ms |
145672 KB |
Output is correct |
2 |
Correct |
917 ms |
145672 KB |
Output is correct |
3 |
Correct |
944 ms |
146176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2526 ms |
188340 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2554 ms |
204412 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2538 ms |
204448 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |