이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
set<int> now;
int n, c, rr;
int k[N], s[N], e[N];
int L[N], R[N];
int fw[N], rmq[18][N];
vector<int> v[N];
int qrymx(int l, int r) {
int bit = 31 - __builtin_clz(r - l + 1);
return max(rmq[bit][l], rmq[bit][r - (1 << bit) + 1]);
}
int query(int x) {
int ans = 0;
for (;x > 0;x -= x & -x) ans += fw[x];
return ans;
}
void update(int x, int w) {
for (;x <= n;x += x & -x) fw[x] += w;
}
int GetBestPosition(int _N, int _C, int _R, int* K, int* S, int* E) {
n = _N, c = _C, rr = _R + 1;
for (int i = 0;i < n - 1;i++) {
k[i + 1] = K[i] + 1;
}
for (int i = 0;i < c;i++) {
s[i + 1] = S[i] + 1;
e[i + 1] = E[i] + 1;
}
for (int i = 1;i <= c;i++) {
int ql = s[i] + query(s[i]), qr = e[i] + query(e[i]);
L[i] = ql, R[i] = qr;
update(L[i] + 1, e[i] - s[i]);
v[L[i]].push_back(i);
v[R[i] + 1].push_back(-i);
//cout << L[i] << ' ' << R[i] << '\n';
}
// for (int i = 1;i <= 5;i++) {
// for (int j = i + 1;j <= 5;j++) {
// deb(i, j);
// }
// }
// RMQ
for (int i = 1;i < n;i++) rmq[0][i] = k[i];
for (int i = 0;i < 17;i++) {
for (int j = 1;j + (2 << i) - 1 < n;j++) rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
}
memset(fw, 0, sizeof fw);
int ans = 0, mx = -1;
for (int i = 1;i <= n;i++) {
for (auto& x : v[i]) {
if (x < 0) now.erase(-x), update(-x, -1);
else now.insert(x), update(x, 1);
}
int l = (*now.begin()) - 1, r = c;
while (l < r) {
int mid = (l + r + 1) / 2;
int x = *now.lower_bound(mid);
int ql = L[x], qr = R[x];
// K[ql, ...,i-1], [i, ..., qr-1]
if (qrymx(ql, qr - 1) < rr) l = mid;
else r = mid - 1;
}
int val = query(l);
if (val > mx) {
mx = val;
ans = i;
}
cout << val << ' ';
}
return ans - 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |