Submission #1009608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009608		hotboy2703	Holiday (IOI14_holiday)	C++14	100 / 100	562 ms	8652 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN=1e5+100;
ll a[MAXN];
vector <ll> b;
ll n,s,d;
pll tree[MAXN*4];
void update(ll id,ll l,ll r,ll i,pll v){
    if (l > i || r < i)return;
    if (l==r){
        tree[id].fi+=v.fi,tree[id].se+=v.se;
        return;
    }
    ll mid = (l + r) >> 1;
    update(id<<1,l,mid,i,v);
    update(id<<1|1,mid+1,r,i,v);
    tree[id].fi=tree[id<<1].fi+tree[id<<1|1].fi;
    tree[id].se=tree[id<<1].se+tree[id<<1|1].se;
}
ll get_kth(ll id,ll l,ll r,ll k){
//    cout<<id<<' '<<l<<' '<<r<<' '<<k<<endl;
    if (l==r){
//        cout<<"WOW "<<tree[id].fi<<' '<<tree[id].se<<' '<<k<<endl;
        if (k >= tree[id].fi)return tree[id].se;
        else return tree[id].se/tree[id].fi*k;
    }
    ll mid = (l + r) >> 1;
    if (tree[id<<1|1].fi >= k)return get_kth(id<<1|1,mid+1,r,k);
    else return get_kth(id<<1,l,mid,k-tree[id<<1|1].fi)+tree[id<<1|1].se;
}
void ins(ll i){
    update(1,0,n-1,a[i],MP(1,b[a[i]]));
}
void del(ll i){
    update(1,0,n-1,a[i],MP(-1,-b[a[i]]));
}
ll res = 0;
ll cur_l,cur_r;
ll query(ll l,ll r,ll k){
//    cout<<"QUERY "<<l<<' '<<r<<' '<<k<<'\n';
    while (cur_l > l)ins(--cur_l);
    while (cur_r < r)ins(++cur_r);
    while (cur_l < l)del(cur_l++);
    while (cur_r > r)del(cur_r--);
//    cout<<"SUS"<<endl;
    ll res = get_kth(1,0,n-1,k);
//    cout<<"WHAT"<<endl;
    return res;
}
void dnc(ll l,ll r,ll optl,ll optr){

    if (l > r)return;
//    cout<<l<<' '<<r<<' '<<optl<<' '<<optr<<'\n';
    ll mid = (l + r) >> 1;
    ll optmid,best;
    optmid = -1,best = -1;
    for (ll x = optl;x <= optr;x ++){
//        cout<<"ST "<<x<<endl;
        ll rem = d-(s+x-2*mid);
        if (rem < 0)continue;
        ll tmp = query(mid,x,rem);
//        cout<<"END "<<x<<endl;
        if (tmp > best){
            tie(best,optmid) = tie(tmp,x);
        }

    }
//    if (optmid==-1)cout<<mid<<endl;
    assert(optmid != -1);
    res = max(res,best);
    dnc(l,mid-1,optl,optmid);
    dnc(mid+1,r,optmid,optr);
}
void solve(){
    memset(tree,0,sizeof tree);
    cur_l = 1;
    cur_r = 0;
    dnc(max(0LL,s-d/2),s,s,n-1);
}
long long int findMaxAttraction(int N, int start, int D, int attraction[]) {
    n=N,s=start,d=D;
    for (ll i = 0;i < n;i ++)a[i] = attraction[i];
    b.resize(n);
    for (ll i = 0;i < n;i ++)b[i] = a[i];
    sort(b.begin(),b.end());

    b.resize(unique(b.begin(),b.end())-b.begin());
    for (ll i = 0;i < n;i ++)a[i] = lower_bound(b.begin(),b.end(),a[i])-b.begin();
    solve();
//    cout<<"OK"<<endl;
    reverse(a,a+n);
    s=n-1-s;
    solve();
    return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve()':
holiday.cpp:84:30: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   84 |     memset(tree,0,sizeof tree);
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from holiday.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53