| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147286 | TAMREF | Holiday (IOI14_holiday) | C++11 | 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>
using namespace std;
using ll = long long;
int a[100005];
int n, st, d;
vector<int> cmp;
struct Segtree{
ll seg[262500];
int cnt[262500];
void init(){
memset(seg, 0, sizeof(seg));
memset(cnt, 0, sizeof(cnt));
}
void upd(int now, int s, int e, int i, int v){
if(i < s || i > e) return;
cnt[now] += v;
seg[now] += v * cmp[i];
if(s == e) return;
int m = s + e >> 1;
upd(now << 1, s, m, i, v);
upd(now << 1 | 1, m+1, e, i, v);
}
ll sum_max_kth(int now, int s, int e, int k){
if(!k) return 0;
if(s == e) return ll(min(cnt[now], k)) * cmp[s];
int m = s + e >> 1;
if(cnt[now << 1 | 1] > k) return sum_max_kth(now<<1|1, m+1, e, k);
else return sum_max_kth(now << 1, s, m, k - cnt[now<<1|1]) + seg[now<<1|1];
}
} S;
map<int, int> M;
bool chk[100005];
void upd(int i, int v){
if((v == 1) == chk[i]) return;
//cout << (v == 1 ? "Add " : "Rmv ") << i << "(val = " << cmp[a[i]] << ")\n";
chk[i] ^= 1;
/*
M[cmp[a[i]]] += v;
if(!M[cmp[a[i]]]) M.erase(cmp[a[i]]);
int summ = 0, cntt = 0;
for(auto p : M) summ += p.first * p.second, cntt += p.second;
for(auto p : M){
summ -= p.first * p.second;
cntt -= p.second;
cout << p.first << ' ' << cntt << ' ' << summ << '\n';
}
*/
S.upd(1, 0, (int)cmp.size() - 1, a[i], v);
}
ll qry(int k){
ll qv = S.sum_max_kth(1, 0, (int)cmp.size() - 1, k);
//cout << "k = " << k << ", qry = " << qv << "\n";
return qv;
}
void init(int N, int S, int D, int A[]){
n = N; st = S; d = D; a = A;
for(int i = 0; i < n; i++){
cmp.push_back(a[i]);
}
sort(cmp.begin(), cmp.end());
cmp.erase( unique(cmp.begin(),cmp.end()), cmp.end() );
for(int i = 0; i < n; i++){
a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();
}
}
ll ans;
void dnc(int s, int e, int kmin, int kmax){ //(e, kmin) maintains painted
//cout << "dnc([" << s << "," << e << "], [" << kmin << "," << kmax << "])\n";
if(s > e) return;
int m = s + e >> 1;
//cout << "m = " << m << "\n";
for(int i = m; i <= e; i++) upd(i, 1);
int klim = min(kmax, 2*m + d - st);
ll lans = 0;
int lansi = kmin;
for(int i = kmin; i <= klim; i++){
//cout << "i = " << i << ", slot = " << 2*m + d - (st+i) << "\n";
upd(i, 1);
ll tmp = qry(d - (st-m) - (i-m));
if(tmp > lans){
lans = tmp;
lansi = i;
}
}
ans = max(ans, lans);
for(int i = klim; i >= lansi; i--) upd(i, -1);
if(m < e){
int mm = (m+1+e) >> 1;
for(int i = m; i <= mm; i++) upd(i, -1);
dnc(m+1, e, lansi, kmax);
}
for(int i = kmax; i >= kmin; i--) upd(i, -1);
if(s < m){
int ss = (s+m-1) >> 1;
for(int i = m; i < min(kmin, e+1); i++) upd(i, 1);
dnc(s, m-1, kmin, lansi);
for(int i = ss; i <= e; i++) upd(i, -1);
}
for(int i = m; i <= e; i++) upd(i, -1);
for(int i = kmin; i <= lansi; i++) upd(i, -1);
}
void pro(){
//cout << "pro\n";
S.init();
memset(chk,0,sizeof(chk));
//M.clear();
int l = max(0, st - d);
int kr = min(n-1, l + d);
dnc(l, st, st, kr);
}
ll findMaxAttraction(int N, int S, int D, int A[]){
ios_base::sync_with_stdio(0); cin.tie(0);
init(N, S, D, A);
pro();
reverse(a, a+n); st = n-1-st;
pro();
return ans;
}