| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 485419 | chienyu_xiong | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#pragma region MACROS
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define int long long int
#define pii pair<int, int>
#define ee end
#define bb begin
#define all(_) begin(_), end(_)
#define smx(y, x) ((y) = max(x, y))
#define smn(y, x) ((y) = min(x, y))
#pragma endregion
void setIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
const int N = 3e5 + 3;
const int inf = 9e12;
const int mod = 1e9 + 7;
int xyz = 1; // test cases
int n, m, s;
int ans;
int fv[N];
int fp[N];
int gv[N];
int gp[N];
vector<int> ord;
vector<int> idx;
vector<int> arr;
class SEG {
public:
int num;
pii seg[N * 4];
void init() {
num = 0;
for (pii &x : seg)
x.first = x.second = 0;
}
void update(int i, int l, int r, int p, bool v) {
int mid = (l + r) / 2;
int il = i << 1 | 0;
int ir = i << 1 | 1;
if (l == r) {
seg[i].S = v;
seg[i].F = v ? arr[ord[mid]] : 0;
return;
}
if (p <= mid + 0) update(il, l, mid + 0, p, v);
if (mid + 1 <= p) update(ir, mid + 1, r, p, v);
seg[i].F = seg[il].F + seg[ir].F;
seg[i].S = seg[il].S + seg[ir].S;
}
int query(int i, int l, int r, int x) {
if (x >= seg[i].second)
return seg[i].first;
int mid = (l + r) / 2;
int il = i << 1 | 0;
int ir = i << 1 | 1;
int res = 0;
if (l != r && x > 0) {
int sum = 0;
res += query(il, l, mid + 0, x - sum); sum += seg[il].second;
res += query(ir, mid + 1, r, x - sum); sum += seg[ir].second;
}
return res;
}
} seg;
void dac(int l, int r, int xl, int xr) {
if (l > r) return;
//cout << l << " " << r << " | " << xl << " " << xr << ": " << seg.seg[1].second << endl;
int mid = (l + r) / 2;
int &best = fp[mid] = s;
int &curr = fv[mid] = 0;
for (int i = xl; i <= xr; i++) {
seg.update(1, 0, n - 1, idx[i], true);
int x = seg.query(1, 0, n - 1, mid - 2 * (i - s));
if (x >= curr) {
best = i;
curr = x;
}
}
if (l != r) {
// deactivate lights
for (int i = xl; i <= xr; i++) {
seg.update(1, 0, n - 1, idx[i], false);
}
// IMPORTANT: left first, right second
dac(l, mid - 0, xl, best);
dac(mid + 1, r, best, xr);
}
}
void one(int l, int r, int xl, int xr) {
if (l > r) return;
int mid = (l + r) / 2;
//cout << l << " " << r << " " << mid << " | " << xl << " " << xr << endl;
int &best = gp[mid] = s - 1;
int &curr = gv[mid] = 0;
for (int i = xr; i >= xl; i--) {
seg.update(1, 0, n - 1, idx[i], true);
int x = seg.query(1, 0, n - 1, mid - (s - i));
if (x > curr) {
best = i;
curr = x;
}
}
if (l != r) {
// deactivate lights
for (int i = xl; i <= xr; i++) {
seg.update(1, 0, n - 1, idx[i], false);
}
// IMPORTANT: right first, left second
one(l, mid - 0, best, xr);
one(mid + 1, r, xl, best);
}
}
bool cmp(int a, int b) {
return arr[a] > arr[b];
}
void slv() {
ord.resize(n);
idx.resize(n);
iota(all(ord), 0);
sort(all(ord), cmp);
for (int i = 0; i < n; i++) {
idx[ord[i]] = i;
}
seg.init(); dac(0, m, s, n - 1);
seg.init(); one(0, m, 0, s - 1);
//for (int i = 0; i <= m; i++) cout << i << ": " << fp[i] << " " << fv[i] << endl;
//for (int i = 0; i <= m; i++) cout << i << ": " << gp[i] << " " << gv[i] << endl;
for (int i = 0; i <= m; i++) {
smx(ans, fv[i] + gv[m - i]);
}
}
int fun() {
slv();
reverse(all(arr)); s = n - 1 - s;
slv();
return ans;
}
int findMaxAttraction(int _n, int _s, int _m, int* vals) {
n = _n;
s = _s;
m = _m;
arr.resize(n);
for (int i = 0; i < n; i++) {
arr[i] = vals[i];
}
return fun();
}
// void run() {
// cin >> n >> m >> s;
// arr.resize(n);
// for (int i = 0; i < n; i++) {
// cin >> arr[i];
// }
// cout << fun() << endl;
// }
// signed main() {
// setIO();
// while (xyz--)
// run();
// return 0;
// }