| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 512109 |
2022-01-16T06:45:30 Z |
blue |
Teams (CEOI11_tea) |
C++17 |
|
2500 ms |
87384 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
const int INF = 100'000'000;
const int Z = (1<<20);
vector<int> segtree;
void set(int i, int v)
{
i += Z;
segtree[i] = v;
for(i >>= 1; i >= 1; i >>= 1) segtree[i] = max(segtree[i<<1], segtree[(i<<1) | 1]);
}
vector<pii> segtree2;
void set2(int i, int v)
{
// cerr << "\n\n" << "set2 " << i << ' ' << v << '\n';
i += Z;
segtree2[i].first = v;
for(i >>= 1; i >= 1; i >>= 1) segtree2[i] = max(segtree2[i<<1], segtree2[(i<<1) | 1]);
// cerr << "root = " << segtree2[1]
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
pii a[1+n];
for(int i = 1; i <= n; i++)
{
cin >> a[i].first;
a[i].second = i;
}
sort(a+1, a+n+1);
int t;
vi dp(1+n);
vi occ[1+n];
vi bit(1+n+1, -INF);
// bit[0 +1] = 0;
for(int j = 0 +1; j <= n +1; j += j&-j) bit[j] = 0;
occ[0].push_back(0);
for(int i = 1; i <= n; i++)
{
t = -INF;
if(a[i].first > i)
{
;
}
else
{
for(int j = i - a[i].first +1; j >= 0 +1; j -= j&-j)
t = max(t, bit[j]+1);
// cerr << i << " -> " << i - a[i].first << '\n';
for(int j = i +1; j <= n +1; j += j&-j)
bit[j] = max(bit[j], t);
}
dp[i] = t;
if(t != -INF) occ[dp[i]].push_back(i);
// cerr << i << " : " << t << '\n';
}
int team_count = dp[n];
// int Z = (1<<20);
int z = 0;
for(int i = 1; i <= n; i++) z = max(z, a[i].first);
int lo = max(n / team_count, z), hi = n;
while(lo != hi)
{
int mxs = (lo+hi)/2;
segtree = vector<int>(Z<<1, -INF);
int l = 0;
int r = -1;
vi new_dp(1+n, -INF);
new_dp[0] = 0;
// cerr << "n = " << n << '\n';
for(int i = 1; i <= n; i++)
{
int nl = max(0, i-mxs);
int nr = max(-1, i - a[i].first);
if(nl > nr) continue;
while(r < nr)
{
r++;
set(r, new_dp[r]);
}
while(l > nl)
{
l--;
set(l, new_dp[l]);
}
while(r > nr)
{
set(r, -INF);
r--;
}
while(l < nl)
{
set(l, -INF);
l++;
}
new_dp[i] = max(-INF, segtree[1]+1);
}
if(new_dp[n] == team_count)
hi = mxs;
else
lo = mxs+1;
}
// cerr << team_count << ' ' << lo << '\n';
int mxs = lo;
// cerr << "\n\n\n\n\n";
// cerr << lo << ' ' << hi << " : " << mxs << '\n';
segtree2 = vector<pii>(Z<<1, {-INF, -1});
for(int i = 0; i <= n; i++) segtree2[Z+i].second = i;
int l = 0;
int r = -1;
vi new_dp(1+n, -INF);
new_dp[0] = 0;
vi prv(1+n, -1);
// cerr << "n = " << n << '\n';
for(int i = 1; i <= n; i++)
{
int nl = max(0, i-mxs);
int nr = max(-1, i - a[i].first);
// if(i-mxs > i - a[i]) con
// cerr << "i = " << i << " : " << "nl nr = " << nl << ' ' << nr << '\n';
if(nl > nr) continue;
// cerr << "journey " << l << ' ' << r << " -> " << nl << ' ' << nr << '\n';
while(r < nr)
{
r++;
set2(r, new_dp[r]);
}
while(l > nl)
{
l--;
set2(l, new_dp[l]);
}
while(r > nr)
{
set2(r, -INF);
r--;
}
while(l < nl)
{
set2(l, -INF);
l++;
}
// cerr << l << ' ' << r << '\n';
// cerr << "st = " << segtree2[1].first << ' ' << segtree2[1].second << '\n';
new_dp[i] = max(-INF, segtree2[1].first+1);
prv[i] = segtree2[1].second;
// cerr << i << " : " << new_dp[i] << ' ' << prv[i] << '\n';
}
vvi teams;
int I = n;
while(I != 0)
{
teams.push_back(vi(0));
// cerr << I << ' ' << prv[I] << '\n';
for(int q = I; q > prv[I]; q--)
teams.back().push_back(a[q].second);
I = prv[I];
}
cout << team_count << '\n';
for(int f = 0; f < team_count; f++)
{
cout << sz(teams[f]) << ' ';
for(int w: teams[f]) cout << w << ' ';
cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16676 KB |
Output is correct |
| 2 |
Correct |
30 ms |
33068 KB |
Output is correct |
| 3 |
Correct |
21 ms |
33164 KB |
Output is correct |
| 4 |
Correct |
28 ms |
33084 KB |
Output is correct |
| 5 |
Correct |
22 ms |
33060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
35 ms |
33188 KB |
Output is correct |
| 3 |
Correct |
37 ms |
33172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
33088 KB |
Output is correct |
| 2 |
Correct |
25 ms |
33108 KB |
Output is correct |
| 3 |
Correct |
34 ms |
33140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
33372 KB |
Output is correct |
| 2 |
Correct |
40 ms |
33364 KB |
Output is correct |
| 3 |
Correct |
56 ms |
33320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
33328 KB |
Output is correct |
| 2 |
Correct |
37 ms |
33324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
37100 KB |
Output is correct |
| 2 |
Correct |
239 ms |
37168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
37552 KB |
Output is correct |
| 2 |
Correct |
238 ms |
36912 KB |
Output is correct |
| 3 |
Correct |
264 ms |
37532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1847 ms |
72224 KB |
Output is correct |
| 2 |
Correct |
1958 ms |
75104 KB |
Output is correct |
| 3 |
Correct |
1766 ms |
72488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2463 ms |
87276 KB |
Output is correct |
| 2 |
Execution timed out |
2560 ms |
87168 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1763 ms |
87384 KB |
Output is correct |
| 2 |
Correct |
282 ms |
74576 KB |
Output is correct |
| 3 |
Execution timed out |
2590 ms |
76920 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
