이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100000;
int t[2 * N];
int sum(int x, int y) { return x + y; }
int mv(int x, int y) { return min(x, y); }
void upd(int l, int r, int v, int (*f)(int, int)) {
l += N;
r += N + 1;
for (; l < r; l /= 2, r /= 2) {
if (l & 1) {
t[l] = f(t[l], v);
l++;
} if (r & 1) {
r--;
t[r] = f(t[r], v);
}
}
}
int get(int x, int s, int (*f)(int, int)) {
for (x += N; x > 0; x /= 2) s = f(s, t[x]);
return s;
}
int bt[2 * 131072], lt[2 * 131072];
void push(int ind, int L, int R) {
if (!lt[ind]) return;
bt[ind] = 0;
if (L != R) {
lt[2 * ind] += lt[ind];
lt[2 * ind + 1] += lt[ind];
}
lt[ind] = 0;
}
void upd2(int l, int r, int L = 0, int R = 131072 - 1, int ind = 1) {
push(ind, L, R);
if (l <= L && R <= r) {
lt[ind] = 1;
push(ind, L, R);
return;
}
if (l > R || L > r) return;
int M = (L + R) / 2;
upd2(l, r, L, M, 2 * ind);
upd2(l, r, M + 1, R, 2 * ind + 1);
bt[ind] = bt[2 * ind] + bt[2 * ind + 1];
}
int ff(int v, int L = 0, int R = 131072 - 1, int ind = 1) {
// if (L == R) cout << "ans " << L << '\n';
if (L == R) return L;
// cout << "! " << L << ' ' << R << ' ' << v << '\n';
int M = (L + R) / 2;
push(2 * ind, L, M);
push(2 * ind + 1, M + 1, R);
int res;
if (bt[2 * ind] >= v) {
res = ff(v, L, M, 2 * ind);
} else {
res = ff(v - bt[2 * ind], M + 1, R, 2 * ind + 1);
}
bt[ind] = bt[2 * ind] + bt[2 * ind + 1];
return res;
}
int brute(int n, int m, int k, int a[], int sl[], int sr[]) {
int res = 0, mx = 0;
for (int p = 0; p <= n; ++p) {
vector<int> v;
int cs = 0;
for (int i = 0; i < n - 1; ++i) v.push_back(a[i]);
if (p == n) v.push_back(k);
else v.insert(v.begin() + p, k);
for (int t = 0; t < m; ++t) {
int w = *max_element(v.begin() + sl[t], v.begin() + sr[t] + 1);
if (w == k) cs++;
v.erase(v.begin() + sl[t], v.begin() + sr[t] + 1);
if (sl[t] != (int)v.size()) v.insert(v.begin() + sl[t], w);
else v.push_back(w);
}
if ((cs > mx)) {
mx = cs;
res = p;
}
}
return res;
}
int GetBestPosition(int n, int m, int k, int *a, int *sl, int *sr) {
for (int i = 0; i < 131072; ++i) {
bt[i + N] = 1;
lt[i] = lt[i + N] = 0;
}
for (int i = 131071; i > 0; --i) {
bt[i] = bt[2 * i] + bt[2 * i + 1];
}
for (int i = 0; i < m; ++i) {
int l = sl[i], r = sr[i];
sl[i] = ff(l + 1);
sr[i] = ff(r + 1);
// cout << l << ' ' << r << '\n';
// cout << sl[i] << ' ' << sr[i] << "\n\n";
upd2(sl[i], sr[i] - 1);
}
vector<int> p(n + 1, 0);
for (int i = 0; i < n - 1; ++i) {
p[i + 1] = p[i] + (k < a[i]);
}
p[n] = p[n - 1];
// time of earliest bad segment
for (int i = 0; i < 2 * N; ++i) {
t[i] = m;
}
// return 0;
for (int i = m - 1; i >= 0; --i) {
assert(sl[i] <= sr[i] && sr[i] <= n - 1);
if (p[sr[i]] - p[sl[i]] != 0) {
upd(sl[i], sr[i], i, mv);
// cout << "! " << sl[i] << ' ' << sr[i] << '\n';
}
}
vector<vector<int>> f(m);
int ans = 0, mx = 0;
for (int i = 0; i < n; ++i) {
int v = get(i, m, mv);
if (v > 0) f[v - 1].push_back(i);
}
// for each f[i] cnt # of segs that contain i
for (int i = 0; i < 2 * N; ++i) {
t[i] = 0;
}
for (int i = 0; i < m; ++i) {
upd(sl[i], sr[i], 1, sum);
for (auto x: f[i]) {
int v = get(x, 0, sum);
// cout << x << ' ' << v << '\n';
if ((v > mx) || (v == mx && x < ans)) {
ans = x;
mx = v;
}
}
}
return ans;
}
// int32_t main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// int n, m, k;
// cin >> n >> m >> k;
// int a[n - 1];
// for (int i = 0; i < n - 1; ++i) cin >> a[i];
// int l[m], r[m];
// for (int i = 0; i < m; ++i) {
// cin >> l[i] >> r[i];
// }
// cout << brute(n, m, k, a, l, r) << '\n';
// cout << GetBestPosition(n, m, k, a, l, r);
// return 0;
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |