Submission #951149

#	Time	Username	Problem	Language	Result	Execution time	Memory
951149		hengliao	Holiday (IOI14_holiday)	C++17	0 / 100	351 ms	20796 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
#define vll vector<ll>
typedef long long ll;

const ll inf=1e18;
const ll mxN=1e5+5;

unordered_map<ll, ll> idx;
unordered_map<ll, ll> vl;
ll ans;
ll s;
ll d;
ll n;
ll val[mxN];
ll de[mxN];

struct segtree1{
    vll tree;
    vll lazy;
    ll treelen;
    void init(ll s){
        tree.clear();
        lazy.clear();
        treelen=s+1;
        while(__builtin_popcountll(treelen)!=1){
            treelen++;
        }
        tree.resize(2*treelen);
        lazy.resize(2*treelen);
    }

    void update(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
        if(low>high) return;
        if(lazy[idx]!=0){
            tree[idx]+=lazy[idx];
            if(low!=high){
                lazy[2*idx]+=lazy[idx];
                lazy[2*idx+1]+=lazy[idx];
            }
            lazy[idx]=0;
        }
        if(low>=qlow && high<=qhigh){
            tree[idx]+=val;
            if(low!=high){
                lazy[2*idx]+=val;
                lazy[2*idx+1]+=val;
            }
            return;
        }
        if(low>qhigh || high<qlow){
            return;
        }
        ll mid=(low+high)/2;
        update(2*idx, low, mid, qlow, qhigh, val);
        update(2*idx+1, mid+1, high, qlow, qhigh, val);
        tree[idx]=max(tree[2*idx], tree[2*idx+1]);
    }

    ll qry(ll idx, ll low, ll high, ll val){
        if(lazy[idx]!=0){
            tree[idx]+=lazy[idx];
            if(low!=high){
                lazy[2*idx]+=lazy[idx];
                lazy[2*idx+1]+=lazy[idx];
            }
            lazy[idx]=0;
        }
        if(tree[idx]<val){
            return -inf;
        }
        if(low==high){
            return low;
        }
        ll mid=(low+high)/2;
        if(tree[2*idx+1]+lazy[2*idx+1]>=val){
            return qry(2*idx+1, mid+1, high, val);
        }
        else{
            return qry(2*idx, low, mid, val);
        }
    }
    ll getval(ll idx, ll low, ll high, ll qlow, ll qhigh){
        if(low>high) return 0;
        if(lazy[idx]!=0){
            tree[idx]+=lazy[idx];
            if(low!=high){
                lazy[2*idx]+=lazy[idx];
                lazy[2*idx+1]+=lazy[idx];
            }
            lazy[idx]=0;
        }
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return 0;
        }
        ll mid=(low+high)/2;
        return max(getval(2*idx, low, mid, qlow, qhigh)
            , getval(2*idx+1, mid+1, high, qlow, qhigh));
    }
};  


struct BIT{
    vll tree;
    ll siz;
    void init(ll s){
        siz=s+1;
        tree.clear();
        tree.resize(siz);
    }

    void update(ll idx, ll val){
        idx++;
        for(;idx<siz;idx+=(idx&-idx)){
            tree[idx]+=val;
        }
    }

    ll getpre(ll idx){
        idx++;
        ll re=0;
        for(;idx>0;idx-=(idx&-idx)){
            re+=tree[idx];
        }
        return re;
    }

    ll getsum(ll a, ll b){
        if(a==0) return getpre(b);
        return getpre(b)-getpre(a-1);
    }
};  

segtree1 seg;
BIT bit;
ll p1;

ll qrylef(ll lef){
    ll id=seg.qry(1, 0, seg.treelen-1, lef);
    if(id==-inf){
        return bit.getsum(0, n-1);
    }
    else{
        ll re=bit.getsum(id, n-1);
        if(seg.getval(1, 0, seg.treelen-1, id, id)>lef){
            re-=bit.getsum(id, id)*(seg.getval(1, 0, seg.treelen-1, id, id)-lef);
        }
        return re;
    }
}

void divi(ll low, ll high, ll qlow, ll qhigh, ll flag){
    if(low>high) return;
    ll mid=(low+high)/2;
    while(p1>mid){
        p1--;
        seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], 1);
        bit.update(idx[val[p1]], val[p1]);
    }
    while(p1<mid){
        seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], -1);
        bit.update(idx[val[p1]], -val[p1]);
        p1++;
    }
    if(flag==1){
        ll cur=-inf;
        ll lef=d-(qlow-mid)-(qlow-s);
        cur=max(cur, qrylef(lef));
        ll op=qlow;
        for(ll i=qlow+1;i<=qhigh;i++){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
            bit.update(idx[val[i]], val[i]);
            lef=d-(i-mid)-(i-s);
            if(lef<=0) break;
            if(qrylef(lef)>cur){
                cur=qrylef(lef);
                op=i;
            }
        }
        ans=max(ans, cur);
        for(ll i=qhigh;i>op;i--){
            lef=d-(i-mid)-(i-s);
            if(lef<=0) continue;
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
            bit.update(idx[val[i]], -val[i]);
        }
        divi(low, mid-1, qlow, op, 0);
        divi(mid+1, high, op, qhigh, 1);
        for(ll i=op;i>qlow;i--){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
            bit.update(idx[val[i]], -val[i]);
        }
    }
    else{
        ll cur=-inf;
        ll lef=d-(qhigh-mid)-(qlow-s);
        ll id=seg.qry(1, 0, seg.treelen-1, lef);
        if(id==-inf){
            cur=max(cur, bit.getsum(0, n-1));
        }
        else{
            cur=max(cur, bit.getsum(id, n-1));
        }
        ll op=qhigh;
        for(ll i=qhigh-1;i>=qlow;i--){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i+1]], -1);
            bit.update(idx[val[i+1]], -val[i]);
            lef=d-(i-mid)-(i-s);
            if(lef<=0) continue;
            if(qrylef(lef)>=cur){
                cur=qrylef(lef);
                op=i;
            }
        }
        ans=max(ans, cur);
        for(ll i=qlow+1;i<=op;i++){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
            bit.update(idx[val[i]], val[i]);
        }
        divi(low, mid-1, qlow, op, 0);
        divi(mid+1, high, op, qhigh, 1);
        for(ll i=op+1;i<=qhigh;i++){
            lef=d-(i-mid)-(i-s);
            if(lef<=0) continue;
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
            bit.update(idx[val[i]], val[i]);
        }
    }
    
}

void divi2(ll low, ll high, ll qlow, ll qhigh, ll flag){
    if(low>high) return;
    ll mid=(low+high)/2;
    while(p1>mid){
        seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], -1);
        bit.update(idx[val[p1]], -val[p1]);
        p1--;
    }
    while(p1<mid){
        p1++;
        seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], 1);
        bit.update(idx[val[p1]], val[p1]);
    }
    if(flag==1){
        ll cur=-inf;
        ll lef=d+(qlow-mid)+(qlow-s);
        if(qrylef(lef)>cur){
            cur=qrylef(lef);
        }
        ll op=qlow;
        for(ll i=qlow+1;i<=qhigh;i++){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
            bit.update(idx[val[i]], -val[i]);
            lef=d+(i-mid)+(i-s);
            if(lef<=0) break;
            if(qrylef(lef)>=cur){
                cur=qrylef(lef);
                op=i;
            }
        }
        ans=max(ans, cur);
        de[mid]=cur;
        for(ll i=qhigh;i>op;i--){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
            bit.update(idx[val[i]], val[i]);
        }
        divi2(low, mid-1, qlow, op, 0);
        divi2(mid+1, high, op, qhigh, 1);
        for(ll i=op;i>qlow;i--){
            lef=d+(i-mid)+(i-s);
            if(lef<=0) continue;
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], 1);
            bit.update(idx[val[i]], val[i]);
        }
    }
    else{
        ll cur=-inf;
        ll lef=d+(qhigh-mid)+(qhigh-s);
        ll id=seg.qry(1, 0, seg.treelen-1, lef);
        if(id==-inf){
            cur=max(cur, bit.getsum(0, n-1));
        }
        else{
            cur=max(cur, bit.getsum(id, n-1));
        }
        ll op=qhigh;
        for(ll i=qhigh-1;i>=qlow;i--){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i+1]], 1);
            bit.update(idx[val[i+1]], val[i]);
            lef=d+(i-mid)+(i-s);
            if(lef<=0) continue;
            if(qrylef(lef)>cur){
                cur=qrylef(lef);
                op=i;
            }
        }
        ans=max(ans, cur);
        de[mid]=cur;
        for(ll i=qlow+1;i<=op;i++){
            lef=d+(i-mid)+(i-s);
            if(lef<=0) continue;
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
            bit.update(idx[val[i]], -val[i]);
        }
        divi2(low, mid-1, qlow, op, 0);
        divi2(mid+1, high, op, qhigh, 1);
        for(ll i=op+1;i<=qhigh;i++){
            seg.update(1, 0, seg.treelen-1, 0, idx[val[i]], -1);
            bit.update(idx[val[i]], -val[i]);
        }
    }
}

ll findMaxAttraction(int tn, int st, int td, int a[]){
    if(td==0) return 0;
    s=st;
    d=td;
    n=tn;
    ans=a[s];
    seg.init(n);
    bit.init(n);
    set<ll> cor;
    for(ll i=0;i<n;i++){
        cor.insert(a[i]);
        val[i]=a[i];
    }
    ll cnt=0;
    for(auto it:cor){
        idx[it]=cnt;
        vl[cnt]=it;
        cnt++;
    }
    p1=s;
    seg.update(1, 0, seg.treelen-1, 0, idx[val[s]], 1);
    bit.update(idx[val[s]], val[s]);
    divi(0, s-1, s, n-1, 1);
    while(p1<s){
        seg.update(1, 0, seg.treelen-1, 0, idx[val[p1]], -1);
        bit.update(idx[val[p1]], -val[p1]);
        p1++;
    }

    divi2(s+1, n-1, 0, s, 0);
    return ans;
}

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