이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Source: https://oj.uz/problem/view/JOI19_cake3
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
const ll N = 2e5 + 10;
// const ll N = 1e5;
#define lc i << 1
#define rc (i << 1) + 1
pair<ll, vi> st[4 * N];
ll n, m;
pii inp[N];
pair<ll, vi> comb(pair<ll, vi> a1, pair<ll, vi> b1) { // MODIFY COMBINER FUNCTION
// combine two sorted vectors
ll i = 0;
ll j = 0;
vi a = a1.s;
vi b = b1.s;
ll sum = 0;
vi vals;
FOR(_, 0, m) {
if (i == a.size() && j == b.size()) break;
if (i == a.size()) {
vals.pb(b[j]);
sum+= b[j];
j++;
} else if (j == b.size()) {
vals.pb(a[i]);
sum+= a[i];
i++;
} else if (a[i] > b[j]) {
vals.pb(a[i]);
sum+= a[i];
i++;
} else {
vals.pb(b[j]);
sum+= b[j];
j++;
}
}
return {sum, vals};
}
void up(ll i) {
st[i] = comb(st[lc], st[rc]);
}
void update(ll ind, ll val, ll i = 1, ll l = 0, ll r = n) { // update pos ind with value val
if (l >= r) return;
if (r - l == 1) {
st[i] = {val, {val}};
return;
}
ll m = (l + r)/2;
if (m > ind) update(ind, val, lc, l, m); // contained in left child
else update(ind, val, rc, m, r); // contained in right child
up(i); // update current index
}
pair<ll, vi> query(ll ql, ll qr, ll i = 1, ll l = 0, ll r = n) { // query from [ql, qr)
if (l >= r) return {0, {}}; // identity
if (ql <= l && qr >= r) { // fully contained
return st[i];
}
if (r - l == 1) return {0, {}}; // leaf node
ll m = (l + r)/2;
pair<ll, vi> acc = {0, {}}; // SET DEFAULT VALUE
if (m >= ql) acc = comb(query(ql, qr, lc, l, m), acc);
if (m <= qr) acc = comb(acc, query(ql, qr, rc, m, r));
return acc;
}
ll ans = -1e18;
void solve(ll ia, ll ib, ll ja, ll jb) { // solves range [ia, ib) assuming the previous DP can be from [ja, jb]
if (ia >= ib) return;
ll i = (ia + ib) / 2;
// if (i-m+1 < ja) {
// solve(i + 1, ib, ja, jb);
// return; // to few numbers
// }
assert(i - m + 1 >= ja);
ll arg_j = 0;
ll opt = -1e18;
for (ll j = ja; j <= i-m+1; j++) {
ll v = query(j, i+1).f - 2 * (inp[i].f - inp[j].f);
// cout << i << j << v << endl;
if (v > opt) {
arg_j = j;
opt = v;
}
}
ans = max(ans, opt);
// solve(ia, i, 0, n);
// solve(i + 1, ib, 0, n);
solve(ia, i, ja, arg_j);
solve(max(arg_j + m - 1, i+1), ib, arg_j, jb);
// ll sum = 0;
// ll opt = 0;
// multiset<ll> vals;
// for (ll j = i; j > i-m; j--) {
// vals.insert(inp[j].s);
// sum+=inp[j].s;
// }
// opt = sum - 2ll * (inp[i].f - inp[i-m+1].f);
// for (ll j = i-m; j >= ja; j--) {
// sum += inp[j].s;
// vals.insert(inp[j].s);
// sum -= *vals.begin();
// vals.erase(vals.begin());
// ll v = sum - 2ll * (inp[i].f - inp[j].f);
// if (v > opt) {
// arg_j = j;
// opt=v;
// }
// }
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
FOR(i, 0, n) cin >> inp[i].s >> inp[i].f;
sort(inp, inp + n);
FOR(i, 0, n) update(i, inp[i].s);
// cout << query(0, 3).f << endl;
solve(m-1, n, 0, n);
cout << ans << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
cake3.cpp: In function 'std::pair<long long int, std::vector<long long int> > comb(std::pair<long long int, std::vector<long long int> >, std::pair<long long int, std::vector<long long int> >)':
cake3.cpp:45:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (i == a.size() && j == b.size()) break;
| ~~^~~~~~~~~~~
cake3.cpp:45:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (i == a.size() && j == b.size()) break;
| ~~^~~~~~~~~~~
cake3.cpp:46:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if (i == a.size()) {
| ~~^~~~~~~~~~~
cake3.cpp:50:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | } else if (j == b.size()) {
| ~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |