| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 564379 | thecodingwizard | 휴가 (IOI14_holiday) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
#define f first
#define s second
#define ii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
const int maxn = 100000;
int n, start, d;
int stIndex[maxn];
struct node {
ll val;
int initVal;
int ct;
} st[maxn*4];
void buildST(int attraction[]) {
vector<ii> attractions;
for (int i = 0; i < n; i++) {
attractions.pb(mp(attraction[i], i));
}
sort(all(attractions));
reverse(all(attractions));
int i = 0;
for (auto x : attractions) {
stIndex[x.s] = i;
i++;
}
auto build = [&](int p, int i, int j, const auto &build)->void {
if (i == j) {
st[p] = node{0, attractions[i].f, 0};
} else {
build(p*2, i, (i+j)/2, build);
build(p*2+1, (i+j)/2+1, j, build);
st[p] = node{0,-1,0};
}
};
build(1, 0, n-1, build);
}
void upd(int p, int i, int j, int k, bool isActive) {
if (i > k || j < k) return;
if (i == j && i == k) {
st[p].val = isActive ? st[p].initVal : 0;
st[p].ct = isActive;
} else {
upd(p*2, i, (i+j)/2, k, isActive);
upd(p*2+1, (i+j)/2+1, j, k, isActive);
st[p].val = st[p*2].val + st[p*2+1].val;
st[p].ct = st[p*2].ct + st[p*2+1].ct;
}
}
ll qry(int p, int i, int j, int k) {
if (st[p].ct <= k) return st[p].val;
if (i == j) return k == 0 ? 0 : st[p].val;
if (st[p*2].ct >= k) return qry(p*2, i, (i+j)/2, k);
return st[p*2].val + qry(p*2+1, (i+j)/2+1, j, k - st[p*2].ct);
}
vector<ll> oneWayLeft(3*maxn), oneWayRight(3*maxn);
void compute(int l, int r, int optl, int optr, vector<ll> &dp) {
if (l > r) return;
int mid = (l+r)/2;
ll best = -1; int bestTransition = -1;
for (int k = optl; k <= optr; k++) {
upd(1, 0, n-1, stIndex[k], 1);
int stepsRemaining = d - k - start;
ll val = qry(1, 0, n-1, stepsRemaining);
if (best < val) {
best = val;
bestTransition = k;
}
}
dp[mid] = best;
for (int k = bestTransition+1; k <= optr; k++) {
upd(1, 0, n-1, stIndex[k], 0);
}
compute(mid+1, r, bestTransition, optr, dp);
for (int k = optl; k <= bestTransition; k++) {
upd(1, 0, n-1, stIndex[k], 0);
}
compute(l, mid-1, optl, bestTransition, dp);
}
long long int findMaxAttraction(int N, int Start, int D, int attraction[]) {
assert(Start == 0);
n = N, start = Start, d = D;
buildST(attraction);
compute(0, d, 0, n-1, oneWayRight);
cout << oneWayRight[d] << endl;
return 0;
}