Submission #362758

#	Time	Username	Problem	Language	Result	Execution time	Memory
362758		Dymo	Holiday (IOI14_holiday)	C++14	100 / 100	1251 ms	8544 KiB

holiday

#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =2e5+10;
const ll mod=1e9+7;
const ll base=1e15;


ll st[4*maxn];
ll st1[4*maxn];
ll val[maxn];
ll pos[maxn];

struct tk
{
    ll n;
    ll l=1;
    ll r=0;
    void update(ll id,ll left,ll right,ll x,ll diff)
    {
        if (x>right||x<left)
            return ;
        if (left==right)
        {
            st[id]+=diff;
            st1[id]+=val[left]*diff;
            return ;
        }
        ll mid=(left+right)/2;
        update(id*2,left,mid, x, diff);
        update(id*2+1,mid+1, right, x, diff);
        st[id]=st[id*2]+st[id*2+1];
        st1[id]=st1[id*2]+st1[id*2+1];
    }
    void finit(ll n1)
    {
        l=1;
        r=0;
        init(1,1,n1);
        n=n1;
    }
    void init(ll id,ll left,ll right)
    {
        st[id]=0;
        st1[id]=0;
        if (left==right)
            return  ;
        ll mid=(left+right)/2;
        init(id*2,left,mid);
        init(id*2+1,mid+1, right);
    }
    void ers(ll t)
    {
        update(1,1,n,t,-1);
    }
    void add(ll t)
    {
        update(1,1,n,t,1);
    }
    ll get1(ll lf,ll rt,ll x)
    {
        if (x<0) return -1e15;
        while (l>lf)
        {
            l--;
            add(pos[l]);
        }
        while (l<lf)
        {
            ers(pos[l]);
            l++;
        }
        while (r<rt)
        {
            r++;
            add(pos[r]);
        }
        while (r>rt)
        {
            ers(pos[r]);
            r--;
        }
        if (x>st[1])
        {
            return st1[1];
        }
        return get(1,1,n,x);
    }
    ll get(ll id,ll left,ll right,ll x)
    {
        if (left==right)
        {
            return val[left]*x;
        }
        ll mid=(left+right)/2;
        if (st[id*2+1]<x)
        {
            return get(id*2,left,mid,x-st[id*2+1])+st1[id*2+1];
        }
        else
        {
            return get(id*2+1,mid+1,right,x);
        }
    }
} man;
ll ans[maxn];
void dac(ll start,ll l,ll r,ll low,ll high,ll d)
{
   if (l>r) return ;
   ll mid=(l+r)/2;
   ll pos_best=-1;
    ans[mid]=-1e15;
   for (int i=low;i<=high;i++)
   {
       ll kc=mid-start;
       if (i!=start)
       {
           kc+=mid-i;
       }
       ll t=man.get1(i,mid,d-kc);
       if (ans[mid]<t)
       {
           ans[mid]=t;
           pos_best=i;
       }
   }
   /*if (mid==5)
   {
       cout <<ans[mid]<<" "<<pos_best<<endl;
   }*/
   dac(start,l,mid-1,low,pos_best,d);
   dac(start,mid+1,r,pos_best,high,d);
}
ll dosth(ll start,ll n,ll d)
{
    man.finit(n);
   // cout <<
   dac(start,start,min(n,start+d),1,start,d);
   ll res=0;
   for (int i=1;i<=n;i++)
   {
       res=max(res,ans[i]);
   }
   return res;
}
ll findMaxAttraction(int n,int start,int d,int attraction[])
{
    vector<ll> vt;
    for (int i=0; i<n; i++)
    {
        pos[i+1]=attraction[i];
        vt.pb(pos[i+1]);
    }
    sort(vt.begin(),vt.end());
    vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    ll siz=vt.size();
    for (int i=1; i<=siz; i++)
    {
        val[i]=vt[i-1];
      //  cout <<val[i]<<" ";
    }
 //   cout <<endl;
    for (int i=1; i<=n; i++)
    {
        pos[i]=lower_bound(vt.begin(),vt.end(),pos[i])-vt.begin()+1;
       //  cout <<pos[i]<<" ";
    }
  //  cout <<endl;
    //cout <<siz<<endl;

    man.finit(n);
    start++;

    ll ans=dosth(start, n,d);
//  cout <<dosth(start,n,d)<<endl;
    reverse(pos+1,pos+n+1);
    ans=max(ans,dosth(n-start+1,n,d));
 /*  for (int i=1;i<=n;i++)
    {
        cout <<pos[i]<<" ";
    }
    cout <<endl;
    cout <<start<<endl;
    cout <<dosth(n-start+1,n,d)<<endl;*/
    return ans;
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    int t[100];
   t[0]=10;
   t[1]=2;
   t[2]=20;
   t[3]=30;
   t[4]=1;
   cout <<findMaxAttraction(5,2,7,t)<<endl;

}*/

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