#include "bits/stdc++.h"
using namespace std;
const int M = 5003;
pair<int, int> seg[M * 2];
void build(int nd, int l, int r, const vector<int>& a) {
if (l == r) {
seg[nd].first = 1;
seg[nd].second = a[l];
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build(nd + 1, l, mid, a);
build(rs, mid + 1, r, a);
seg[nd].first = seg[nd + 1].first + seg[rs].first;
seg[nd].second = max(seg[nd + 1].second, seg[rs].second);
}
void upd(int nd, int l, int r, int p) {
if (l == r) {
seg[nd].first = seg[nd].second = 0;
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p);
} else {
upd(rs, mid + 1, r, p);
}
seg[nd].first = seg[nd + 1].first + seg[rs].first;
seg[nd].second = max(seg[nd + 1].second, seg[rs].second);
}
int getfirstpos(int nd, int l, int r, int k) {
if (l == r) {
return (k == seg[nd].first ? l : -1);
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
int ret = getfirstpos(nd + 1, l, mid, k);
if (ret == -1) {
ret = getfirstpos(rs, mid + 1, r, k - seg[nd + 1].first);
}
return ret;
}
int getmx(int nd, int l, int r, int s, int e) {
if (l >= s && r <= e) {
return seg[nd].second;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
return getmx(nd + 1, l, mid, s, e);
} else {
if (mid < s) {
return getmx(rs, mid + 1, r, s, e);
} else {
return max(getmx(nd + 1, l, mid, s, e), getmx(rs, mid + 1, r, s, e));
}
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int ret = 0;
for (int i = 0; i < N; ++i) {
int pos = i, tmp = 0;
vector<int> a(N);
a[pos] = R;
for (int j = 0; j < pos; ++j) {
a[j] = K[j];
}
for (int j = pos + 1; j < N; ++j) {
a[j] = K[j - 1];
}
build(0, 0, N - 1, a);
for (int j = 0; j < C; ++j) {
int l = S[j], r = E[j];
int al = getfirstpos(0, 0, N - 1, l + 1);
int ar = getfirstpos(0, 0, N - 1, r + 1);
int mx = getmx(0, 0, N - 1, al, ar);
//if (i == 0) {
//cout << "l, r, mx: " << al << ' ' << ar << ' ' << mx << '\n';
//}
if (mx == R) {
tmp++;
}
for (int k = al, cnt = 0; k <= ar && k != -1;) {
if (a[k] != mx) {
//cout << "K: " << k << '\n';
upd(0, 0, N - 1, k);
} else {
cnt++;
}
k = getfirstpos(0, 0, N - 1, l + 1 + cnt);
//if (k == 0 || k == ar) break;
}
}
//cout << "I : " << i << ' ' << tmp << '\n';
ret = max(ret, tmp);
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1032 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
