이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <llint, llint> pi;
const int MAXN = 2000005;
const llint INF = 1000000000000000000LL;
int n, k, T, ofs = 1, cnt;
int t[MAXN], lim[MAXN], add[MAXN];
llint mx[75005 * 4], br[75005 * 4], prop[75005 * 4];
pi dp[MAXN];
set <int> st;
vector <int> v[MAXN];
void build () {
for (int i = 1; i <= n; i++) {
int j = i + T - t[i];
if (i <= j) {
st.insert(i);
if (j + 1 <= n) v[j + 1].push_back(i);
}
for (auto x : v[i]) {
st.erase(x);
}
if (!st.empty()) {
lim[i] = *st.rbegin();
if (lim[i] < i) add[lim[i]]++;
cnt++;
} else {
lim[i] = 1e9;
}
//cout << "bla " << i << " " << lim[i] << endl;
}
}
void upd (int x, pi novi) {
x += ofs;
mx[x] = novi.first;
br[x] = novi.second;
x /= 2;
while (x > 0) {
pi lef = {mx[2 * x] + prop[2 * x], br[2 * x]};
pi rig = {mx[2 * x + 1] + prop[2 * x + 1], br[2 * x + 1]};
pi res = max(lef, rig);
mx[x] = res.first;
br[x] = res.second;
x /= 2;
}
}
pi update (int x, int from, int to, int lo, int hi, int val) {
if (from <= lo && hi <= to) {
prop[x] += val;
return {mx[x] + prop[x], br[x]};
}
if (to < lo || hi < from) return {-INF, -INF};
pi lef = update(2 * x, from, to, lo, (lo + hi) / 2, val);
pi rig = update(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi, val);
pi res = max(lef, rig);
mx[x] = res.first;
br[x] = res.second;
return {mx[x] + prop[x], br[x]};
}
pi calc (llint cost) {
for (int i = 0; i < 2 * ofs; i++) {
mx[i] = -INF; br[i] = -INF;
prop[i] = 0;
}
upd(0, {0, 0});
pi res = {0, 0};
int curr = 0;
for (int i = 1; i <= n; i++) {
curr += add[i];
if (lim[i] < i) {
update(1, lim[i], i - 1, 0, ofs - 1, 1);
curr--;
}
dp[i] = {mx[1] + curr - cost, br[1] - 1};
upd(i, {dp[i].first - curr, dp[i].second});
res = max(res, dp[i]);
}
return res;
}
llint bs () {
llint lo = 0, hi = 1e9;
while (lo < hi) {
int mid = (lo + hi) / 2;
pi res = calc(mid);
if (-res.second > k) {
lo = mid + 1;
} else {
hi = mid;
}
}
pi res = calc(lo);
return res.first + lo * k;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> T;
while (ofs < n + 1) ofs *= 2;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
build();
pi res = calc(0);
//cout << res.first << " " << res.second;
cout << cnt - bs();
/*for (int i = 0; i < 10; i++) {
pi res = calc(i);
cout << "bla " << i << " " << res.first << " " << -res.second << endl;
}*/
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
prison.cpp: In function 'int main()':
prison.cpp:113:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
113 | pi res = calc(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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |