| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1277016 | trandangquang | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define task "test"
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define vii vector <ii>
#define vi vector <int>
#define fi first
#define se second
#define int long long
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
const int NX = 250005;
int n, st, d, att[NX], upto[20]; ii bestr[NX], bestl[NX];
vi rar;
/// bestr[u] = {gia tri, vi tri gan nhat} khi di voi thoi gian u
/// bestl[u]: tuong tu voi bestr[u]
struct segmentTree {
struct node {
int num = 0;
ll sum = 0;
} st[NX<<2];
void reset() {
node tmp = {0, 0};
fill(begin(st), end(st), tmp);
}
void upd(int x, int val) {
int id=1, l=1, r=sz(rar);
while(1) {
if(l==r) break;
int m=(l+r)>>1;
if(x<=m) {
id = id<<1;
r=m;
}
else {
id = id<<1|1;
l=m+1;
}
}
st[id].num += val;
st[id].sum += val*rar[x-1];
while(id>1) {
id /= 2;
st[id].num = st[id<<1].num + st[id<<1|1].num;
st[id].sum = st[id<<1].sum + st[id<<1|1].sum;
}
}
ll get_max(int nli) {
int id=1, l=1, r=sz(rar);
ll res = 0;
while(l<=r) {
if(l==r) break;
int m=(l+r)>>1;
if(st[id<<1|1].num <= nli) {
nli-=st[id<<1|1].num;
res+=st[id<<1|1].sum;
id=id<<1;
r=m;
}
else {
id=id<<1|1;
l=m+1;
}
}
return res + min(nli, st[id].num)*rar[l-1];
}
} smt[20];
void calcr(int L, int R, int optL, int optR, int lvl) {
// printf("Range: %d %d, optRange: %d %d\n", L, R, optL, optR);
if(L > R) return;
int mid = (L+R) >> 1;
FOR(i, optL, optR) {
if(mid-(i-st) < 0) break; /// neu nhu di qua xa -> break
while(upto[lvl] < i) smt[lvl].upd(att[++upto[lvl]], 1);
int nwVal = smt[lvl].get_max(mid-(i-st));
if(nwVal > bestr[mid].fi) {
bestr[mid].fi = nwVal;
bestr[mid].se = i;
}
}
calcr(L, mid-1, optL, bestr[mid].se, lvl+1);
calcr(mid+1, R, bestr[mid].se, optR, lvl+1);
}
void calcl(int L, int R, int optL, int optR, int lvl) {
// printf("Range: %d %d, optRange: %d %d\n", L, R, optL, optR);
if(L > R) return;
int mid = (L+R) >> 1;
FORD(i, optR, optL) {
if(mid-(st-i) < 0) break; ///
while(upto[lvl] > i) smt[lvl].upd(att[--upto[lvl]], 1);
int nwVal = smt[lvl].get_max(mid-(st-i));
// if(mid == 3) cout << i << " " << nwVal << " " << mid-(st-i) << '\n';
if(nwVal > bestl[mid].fi) {
bestl[mid].fi = nwVal;
bestl[mid].se = i;
}
}
// cout << mid << " " << bestl[mid].se<<" "<<bestl[mid].fi<<'\n';
calcl(L, mid-1, bestl[mid].se, optR, lvl+1);
calcl(mid+1, R, optL, bestl[mid].se, lvl+1);
}
ll findMaxAttraction(int N, int ST, int D, int attraction[]){
n=N; st=ST; d=D;
++st;
FOR(i, 1, n) {
att[i]=attraction[i-1];
rar.eb(att[i]);
}
sort(all(rar));
FOR(i, 1, n) {
att[i] = upper_bound(all(rar), att[i]) - rar.begin();
}
FOR(i, 1, d) bestl[i].fi = bestr[i].fi = -1;
FOR(i, 1, 19) upto[i] = st;
calcr(1, d, st+1, n, 1);
FOR(i, 1, 19) {
smt[i].reset();
upto[i] = st;
}
calcl(1, d, 1, st-1, 1);
int ans = 0;
FOR(i, 0, d) {
if(d-i-(bestr[i].se-st)>=0) {
ans = max(ans, bestr[i].fi + bestl[d-i-(bestr[i].se-st)].fi);
}
if(d-i-(st-bestl[i].se)>=0) {
ans = max(ans, bestl[i].fi + bestr[d-i-(st-bestl[i].se)].fi);
}
ans = max(ans, bestl[i].fi);
ans = max(ans, bestr[i].fi);
}
--d;
FOR(i, 0, d) {
if(d-i-(bestr[i].se-st)>=0) {
ans = max(ans, bestr[i].fi + bestl[d-i-(bestr[i].se-st)].fi + rar[att[st] - 1]);
}
if(d-i-(st-bestl[i].se)>=0) {
ans = max(ans, bestl[i].fi + bestr[d-i-(st-bestl[i].se)].fi + rar[att[st] - 1]);
}
ans = max(ans, bestl[i].fi + rar[att[st] - 1]);
ans = max(ans, bestr[i].fi + rar[att[st] - 1]);
}
return ans;
}