Submission #245992

#	Time	Username	Problem	Language	Result	Execution time	Memory
245992		gs18115	Holiday (IOI14_holiday)	C++14	100 / 100	267 ms	54264 KiB

holiday

#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct node
{
    int cnt;
    ll sum;
    int l,r;
    node(){sum=0;cnt=l=r=0;}
}tree[2222222];
int tct;
void upd(int&n,int s,int e,int x,int p)
{
    tree[++tct]=tree[n];
    n=tct;
    tree[n].cnt++;
    tree[n].sum+=p;
    if(s==e)
        return;
    int m=s+(e-s)/2;
    if(x>m)
        upd(tree[n].r,m+1,e,x,p);
    else
        upd(tree[n].l,s,m,x,p);
    return;
}
ll query(int l,int r,int k)
{
    if(k<=0)
        return 0;
    if(k>=tree[r].cnt-tree[l].cnt)
        return tree[r].sum-tree[l].sum;
    if(tree[r].l==0&&tree[r].r==0)
        return k*(tree[r].sum/tree[r].cnt);
    node&ln=tree[tree[l].r];
    node&rn=tree[tree[r].r];
    if(k>=rn.cnt-ln.cnt)
        return(rn.sum-ln.sum)+query(tree[l].l,tree[r].l,k-(rn.cnt-ln.cnt));
    return query(tree[l].r,tree[r].r,k);
}
int rt[100010];
int n,st,d;
ll ans;
void dnc1(int s,int e,int as,int ae)
{
    if(s>e)
        return;
    int m=s+(e-s)/2;
    int mxi=-1;
    ll cans=-1;
    for(int i=as;i<=ae;i++)
    {
        ll cur=query(rt[i-1],rt[m],d-(st+m-i*2));
        if(cur>cans)
            cans=cur,mxi=i;
    }
    ans=max(ans,cans);
    dnc1(s,m-1,as,mxi);
    dnc1(m+1,e,mxi,ae);
    return;
}
void dnc2(int s,int e,int as,int ae)
{
    if(s>e)
        return;
    int m=s+(e-s)/2;
    int mxi=-1;
    ll cans=-1;
    for(int i=as;i<=ae;i++)
    {
        ll cur=query(rt[m-1],rt[i],d-(i*2-st-m));
        if(cur>cans)
            cans=cur,mxi=i;
    }
    ans=max(ans,cans);
    dnc2(s,m-1,as,mxi);
    dnc2(m+1,e,mxi,ae);
    return;
}
long long int findMaxAttraction(int n,int start,int d,int attraction[])
{
    ::n=n;
    ::st=start+1;
    ::d=d;
    vector<int>v(n);
    for(int i=0;i<n;i++)
        v[i]=attraction[i];
    vector<int>cv=v;
    sort(all(cv));
    cv.erase(unique(all(cv)),cv.end());
    int m=cv.size();
    v.insert(v.begin(),0);
    for(int i=0;i++<n;)
        upd(rt[i]=rt[i-1],1,m,upper_bound(all(cv),v[i])-cv.begin(),v[i]);
    dnc1(st,min(n,st+d-1),1,st);
    dnc2(max(1,st-d+1),st,st,n);
    return ans;
    return 0;
}

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