#include <bits/stdc++.h>
using namespace std;
class BIT {
public:
vector<int>bit; int size_;
void init(int sz) {
size_ = sz + 2;
bit.resize(size_ + 2, 0);
}
void add(int pos, int x) {
pos++;
while (pos <= size_) {
bit[pos] += x; pos += (pos & -pos);
}
}
int sum(int pos) {
pos++; int s = 0;
while (pos >= 1) {
s += bit[pos]; pos -= (pos & -pos);
}
return s;
}
int getval(int pos) {
int L = 0, R = size_ + 1, M, minx = (1 << 30);
for (int i = 0; i < 20; i++) {
M = (L + R) / 2;
int G = sum(M); //cout << "! " << pos << " " << M << " " << G << " " << minx << endl;
if (G >= pos) { minx = min(minx, M); R = M; }
else { L = M; }
}
return minx;
}
};
class RangeMax {
public:
vector<int>dat; int size_;
void init(int sz) {
size_ = 1;
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, 0);
}
void update(int pos, int x) {
pos += size_; dat[pos] = x;
while (pos >= 2) {
pos /= 2;
dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
}
}
int query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (r <= a || b <= l) return 0;
int c1 = query_(l, r, a, (a + b) >> 1, u * 2);
int c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return max(c1, c2);
}
int query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
vector<int> X[200009]; pair<int, int> dp[200009][3], dpr[200009][3]; int cl[200009], cr[200009], A[200009], reality, NN;
BIT Z; RangeMax Y; set<pair<int, int>> Set;
void dfs(int pos) {
if (X[pos].size() == 0) {
if (pos < NN - 1) dp[pos][0] = make_pair(0, -1000000);
dp[pos][1] = make_pair(0, -pos);
if (pos >= 1) dp[pos][2] = make_pair(0, -1000000);
return;
}
for (int i = 0; i < (int)X[pos].size(); i++) dfs(X[pos][i]);
for (int i = 0; i <= (int)X[pos].size(); i++) { for (int j = 0; j <= 2; j++) dpr[i][j] = make_pair(-(1<<30),-1000000); }
dpr[0][0] = make_pair(0, -1000000);
for (int i = 0; i < (int)X[pos].size(); i++) {
for (int j = 0; j < 3; j++) {
if (j != 1) dpr[i + 1][j] = max(dpr[i + 1][j], make_pair(dpr[i][j].first + dp[X[pos][i]][j].first, max(dpr[i][j].second, dp[X[pos][i]][j].second)));
if (j <= 1) dpr[i + 1][j + 1] = max(dpr[i + 1][j + 1], make_pair(dpr[i][j].first + dp[X[pos][i]][j + 1].first, max(dpr[i][j].second, dp[X[pos][i]][j+1].second)));
}
}
pair<int, int> V1 = dpr[X[pos].size()][0], V2 = max(dpr[X[pos].size()][1], dpr[X[pos].size()][2]);
for (int i = 0; i <= (int)X[pos].size(); i++) { for (int j = 0; j <= 2; j++) dpr[i][j] = make_pair(-(1<<30),-1000000); }
dpr[0][2] = make_pair(0, -1000000);
for (int i = 0; i < (int)X[pos].size(); i++) {
for (int j = 0; j < 3; j++) {
if (j != 1) dpr[i + 1][j] = max(dpr[i + 1][j], make_pair(dpr[i][j].first + dp[X[pos][i]][j].first, max(dpr[i][j].second, dp[X[pos][i]][j].second)));
if (j <= 1) dpr[i + 1][j + 1] = max(dpr[i + 1][j + 1], make_pair(dpr[i][j].first + dp[X[pos][i]][j + 1].first, max(dpr[i][j].second, dp[X[pos][i]][j+1].second)));
}
}
pair<int, int> V3 = dpr[X[pos].size()][2];
dp[pos][0] = V1;
dp[pos][1] = V2; if (dp[pos][1].first >= 0 && Y.query(cl[pos], cr[pos]) <= reality) dp[pos][1].first++;
dp[pos][2] = V3;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
Z.init(N); Y.init(N); reality = R; NN = N;
for (int i = 0; i < N; i++) { Z.add(i, 1); Set.insert(make_pair(i, i)); }
for (int i = 0; i < 600009; i++) dp[i / 3][i % 3] = make_pair(-(1 << 30), -1000000);
for (int i = 0; i < N - 1; i++) { A[i] = K[i]; Y.update(i, A[i]); }
for (int i = 0; i < C; i++) {
int TL = (1 << 30), TR = N;
for (int j = 0; j < E[i] - S[i] + 1; j++) {
int G = Z.getval(S[i] + 1);
TL = min(TL, G); Z.add(G, -1);
}
TR = min(TR, Z.getval(S[i] + 1));
auto itr = Set.lower_bound(make_pair(TL, 0));
while (itr != Set.end()) {
pair<int, int> Z = *itr;
if (Z.first >= TR) break;
Set.erase(itr); X[N + i].push_back(Z.second);
itr = Set.lower_bound(make_pair(TL, 0));
}
Z.add(TL, 1); Set.insert(make_pair(TL, N + i));
cl[N + i] = TL; cr[N + i] = TR - 1; //cout << N + i << " " << cl[N + i] << " " << cr[N + i] << endl;
}
dfs(N + C - 1);
/*for (int i = 0; i <= N + C - 1; i++) {
cout << i << ": " ;
for (int j = 0; j < 3; j++) {
cout << "(" << dp[i][j].first << ", " << dp[i][j].second << ") ";
}
cout << endl;
}*/
return -dp[N + C - 1][1].second;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
13 ms |
9856 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9856 KB |
Output is correct |
| 7 |
Correct |
14 ms |
9884 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 10 |
Correct |
14 ms |
9728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 2 |
Correct |
19 ms |
10880 KB |
Output is correct |
| 3 |
Correct |
15 ms |
10232 KB |
Output is correct |
| 4 |
Correct |
27 ms |
10496 KB |
Output is correct |
| 5 |
Correct |
19 ms |
10616 KB |
Output is correct |
| 6 |
Correct |
16 ms |
10368 KB |
Output is correct |
| 7 |
Correct |
23 ms |
10624 KB |
Output is correct |
| 8 |
Correct |
25 ms |
10488 KB |
Output is correct |
| 9 |
Correct |
15 ms |
10240 KB |
Output is correct |
| 10 |
Correct |
28 ms |
10240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
13768 KB |
Output is correct |
| 2 |
Correct |
280 ms |
31332 KB |
Output is correct |
| 3 |
Correct |
104 ms |
19648 KB |
Output is correct |
| 4 |
Correct |
237 ms |
24312 KB |
Output is correct |
| 5 |
Correct |
231 ms |
26488 KB |
Output is correct |
| 6 |
Correct |
289 ms |
19064 KB |
Output is correct |
| 7 |
Correct |
214 ms |
26616 KB |
Output is correct |
| 8 |
Correct |
217 ms |
26720 KB |
Output is correct |
| 9 |
Correct |
92 ms |
19176 KB |
Output is correct |
| 10 |
Correct |
123 ms |
17372 KB |
Output is correct |
