| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 516108 |
2022-01-20T11:39:14 Z |
blue |
Teams (CEOI11_tea) |
C++17 |
|
2116 ms |
115048 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);
template <class MyType>
class MySegTree {
public:
vector<MyType> segtree;
MySegTree(MyType defaultValue)
{
segtree = vector<MyType>(Z<<1, defaultValue);
}
void set(int i, MyType v)
{
i += Z;
segtree[i] = v;
for(i /= 2; i >= 1; i /= 2) segtree[i] = max(segtree[i*2], segtree[(i*2) | 1]);
}
MyType query()
{
return segtree[1];
}
};
MySegTree<int> segtree(-INF);
MySegTree<pii> segtree2({-INF, 0});
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);
vi dp(1+n);
vi dpmx(1+n);
dp[0] = dpmx[0] = 0;
for (int i = 1; i <= n; i++)
{
if (i - a[i].first >= 0)
dp[i] = dpmx[i - a[i].first] + 1;
else
dp[i] = -INF;
dpmx[i] = max(dp[i], dpmx[i-1]);
// cerr << i << " : " << dp[i] << '\n';
}
int team_count = dp[n];
int lo = 1, hi = n;
while(lo != hi)
{
int mxs = (lo+hi)/2;
// segtree.segtree = vector<int>(Z<<1, -INF);
segtree = MySegTree(-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;
if(nr - nl < 40)
{
for(int g = nl; g <= nr; g++)
new_dp[i] = max(new_dp[i], new_dp[g]+1);
continue;
}
while(r < nr)
{
r++;
segtree.set(r, new_dp[r]);
}
while(l > nl)
{
l--;
segtree.set(l, new_dp[l]);
}
while(r > nr)
{
segtree.set(r, -INF);
r--;
}
while(l < nl)
{
segtree.set(l, -INF);
l++;
}
new_dp[i] = max(-INF, segtree.query()+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 = MySegTree(pii{-INF, -1});
for(int i = 0; i <= n; i++) segtree2.segtree[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(nr - nl < 20)
{
for(int i2 = nl; i2 <= nr; i2++)
{
if(new_dp[i2]+1 >= new_dp[i])
{
new_dp[i] = new_dp[i2] + 1;
prv[i] = i2;
}
}
continue;
}
// 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++;
segtree2.set(r, {new_dp[r], r});
}
while(l > nl)
{
l--;
segtree2.set(l, {new_dp[l], l});
}
while(r > nr)
{
segtree2.set(r, {-INF, r});
r--;
}
while(l < nl)
{
segtree2.set(l, {-INF, l});
l++;
}
// cerr << l << ' ' << r << '\n';
// cerr << "st = " << segtree2[1].first << ' ' << segtree2[1].second << '\n';
new_dp[i] = max(-INF, segtree2.query().first+1);
prv[i] = segtree2.query().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 |
16 ms |
41320 KB |
Output is correct |
| 2 |
Correct |
27 ms |
49536 KB |
Output is correct |
| 3 |
Correct |
29 ms |
49476 KB |
Output is correct |
| 4 |
Correct |
27 ms |
49492 KB |
Output is correct |
| 5 |
Correct |
27 ms |
49524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
49528 KB |
Output is correct |
| 2 |
Correct |
39 ms |
49608 KB |
Output is correct |
| 3 |
Correct |
30 ms |
49468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
49496 KB |
Output is correct |
| 2 |
Correct |
34 ms |
49536 KB |
Output is correct |
| 3 |
Correct |
32 ms |
49504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
49628 KB |
Output is correct |
| 2 |
Correct |
41 ms |
49636 KB |
Output is correct |
| 3 |
Correct |
45 ms |
49600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
49608 KB |
Output is correct |
| 2 |
Correct |
42 ms |
49564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
51276 KB |
Output is correct |
| 2 |
Correct |
174 ms |
51076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
51444 KB |
Output is correct |
| 2 |
Correct |
132 ms |
50928 KB |
Output is correct |
| 3 |
Correct |
177 ms |
51368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1627 ms |
64932 KB |
Output is correct |
| 2 |
Correct |
1237 ms |
63516 KB |
Output is correct |
| 3 |
Correct |
1473 ms |
65660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1998 ms |
70048 KB |
Output is correct |
| 2 |
Correct |
1982 ms |
115048 KB |
Output is correct |
| 3 |
Correct |
1654 ms |
68172 KB |
Output is correct |
| 4 |
Correct |
1861 ms |
68204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1043 ms |
70040 KB |
Output is correct |
| 2 |
Correct |
264 ms |
69096 KB |
Output is correct |
| 3 |
Correct |
2116 ms |
69088 KB |
Output is correct |
| 4 |
Correct |
1976 ms |
67384 KB |
Output is correct |
