| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1082880 | phong | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 15, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m;
pii a[nmax];
ll best[nmax];
multiset<pii> one, two;
struct node{
int l, r, from, to;
};
vector<node> adj[50];
ll pre[nmax], suf[nmax];
int el[nmax];
pii b[nmax];
struct hos{
int cnt, w;
}tree[nmax << 2];
void update(int id, int l, int r, int u, int idx){
if(l > u || r < u) return;
if(l >= u && r <= u){
if(idx){
tree[id].cnt = 1;
tree[id].w = b[l].fi;
return;
}
else {
tree[id].cnt = 0;
tree[id].w = 0;
return;
}
}
int mid= r + l >> 1;
update(id << 1, l, mid, u, idx);
update(id << 1 | 1, mid + 1, r, u, idx);
tree[id].cnt = tree[id << 1].cnt + tree[id << 1 | 1].cnt;
tree[id].w = tree[id << 1].w + tree[id << 1 | 1].w;
}
int get(int id, int l, int r, int u, int v, int k){
if(tree[id].cnt <= k) return tree[id].w;
int mid = r + l >> 1;
if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v, k);
if(mid + 1 > v) return get(id << 1, l, mid, u, v, k);
if(k <= tree[id << 1].cnt) return get(id << 1, l, mid, u, v, k);
return tree[id << 1].w + get(id << 1 | 1, mid + 1, r, u,v, k - tree[id << 1].cnt);
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
sort(a + 1, a + 1 + n, [](pii a, pii b){
return a.se < b.se;
});
for(int i = 1; i <= n; ++i) b[i] = {a[i].fi, i};
sort(b + 1, b + 1 + n, [](pii a, pii b){
return a.fi > b.fi;
});
for(int i = 1; i <= n; ++i) el[b[i].se] = i;
pre[0] = suf[n + 1] = -oo;
for(int i = 1; i <= n; ++i){
pre[i] = max(pre[i - 1], a[i].fi + 2 * a[i].se);
}
// cout << pre[1] << ' ';
for(int i = n; i >= 1; --i){
suf[i] = max(suf[i + 1], a[i].fi - 2 * a[i].se);
}
adj[1].push_back({1, n, 1, n});
ll ans = -oo;
for(int e = 1; e <= 20; ++e){
if(adj[e].empty()) continue;
int pos = 1, pre_pos = 1;
ll cur = 0;
for(int i = 1; i <= n; ++i) update(1, 1, n, i, 0);
for(auto [l, r, from, to] : adj[e]){
int mid = r + l >> 1;
auto &p = best[mid];
p = to;
int ma = -oo;
for(int i = from; i <= to; ++i){
if(i - mid + 1 < m) continue;
while(pos < i){
update(1, 1, n, el[pos], 1);
++pos;
}
while(pre_pos <= mid){
update(1, 1, n, el[pre_pos], 0);
++pre_pos;
}
ll res = pre[mid] + suf[i] + get(1, 1, n, 1, n, m - 2);
// cout << res << ' ';
if(ma < res){
ma = res;
p = i;
ans = max(ans, ma);
}
}
if(l < mid) adj[e + 1].push_back({l, mid - 1, from, p});
if(mid < r) adj[e + 1].push_back({mid + 1, r, p, to});
}
}
// debug(best, n);
cout << ans;
}
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 3 4
*/