Submission #731752

#	Time	Username	Problem	Language	Result	Execution time	Memory
731752		ogibogi2004	Holiday (IOI14_holiday)	C++14	100 / 100	930 ms	34128 KiB

holiday

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

const ll MAXN=1e5+6;
const int MAXT=3e5+6;
const ll INF=2e13;
ll att[MAXN];
ll low[MAXT],high[MAXT],n1,start1,d1;
priority_queue<ll> pq;
ll cur_sum;
ll fr[MAXT],ansr[MAXT];
ll fl[MAXT],ansl[MAXT];
//start1 will be in left
vector<ll> what_to_check[MAXN];
struct node
{
    ll cnt_cities;
    ll sum;
};
struct segment_tree
{
    node tree[3*MAXN];
    void init()
    {
        for(ll j=0;j<3*MAXN;j++)
        {
            tree[j].cnt_cities=0;
            tree[j].sum=0;
        }
    }
    void update(ll l,ll r,ll idx,ll pos,ll val)
    {
        if(l>pos)return;
        if(r<pos)return;
        if(l==r)
        {
            tree[idx].cnt_cities=1;
            tree[idx].sum=val;
            return;
        }
        ll mid=(l+r)/2;
        update(l,mid,idx*2,pos,val);
        update(mid+1,r,idx*2+1,pos,val);
        tree[idx].cnt_cities=tree[idx*2].cnt_cities+tree[idx*2+1].cnt_cities;
        tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;
    }
    ll query(ll l,ll r,ll idx,ll cnt_needed)
    {
        if(cnt_needed<0)return -INF;
        if(cnt_needed==0)return 0;
        if(cnt_needed>=tree[idx].cnt_cities)return tree[idx].sum;
        //cout<<l<<" "<<r<<" "<<tree[idx].cnt_cities<<" "<<cnt_needed<<endl;
        ll mid=(l+r)/2;
        if(tree[idx*2+1].cnt_cities>=cnt_needed)return query(mid+1,r,idx*2+1,cnt_needed);
        else return tree[idx*2+1].sum+query(l,mid,idx*2,cnt_needed-tree[idx*2+1].cnt_cities);
    }
}tr;
ll num[MAXN];
void compute_right(ll factor)
{
    ll max_time=(n1-start1)*factor+(n1-start1);
    vector<pair<ll,ll> >llervals;
    vector<pair<ll,ll> >new_llervals;
    llervals.push_back({0,max_time});
    for(;llervals.size()>0;)
    {
        //memset(what_to_check,-1,sizeof(what_to_check));
        //cout<<"??1\n";
        for(auto xd:llervals)
        {
            ll mid=(xd.first+xd.second)/2;
            if(xd.first-1>=0)low[mid]=ansr[xd.first-1];
            else low[mid]=start1;
            if(xd.second+1<=max_time)high[mid]=ansr[xd.second+1];
            else high[mid]=n1;
            //cout<<mid<<" "<<low[mid]<<" "<<high[mid]<<endl;
            for(ll j=low[mid];j<=high[mid];j++)
            {
                //cout<<"*"<<j<<endl;
                what_to_check[j].push_back(mid);
            }
        }
        //cout<<"??2\n";
        tr.init();
        for(ll i=start1;i<=n1;i++)
        {
            if(i!=start1)tr.update(1,n1,1,num[i],att[i]);
            for(auto time1:what_to_check[i])
            {
                if(time1==-1)continue;
                ll gg=tr.query(1,n1,1,time1-(i-start1)*factor);
                //cout<<"update right"<<time1<<" "<<gg<<endl;
                if(gg>fr[time1])
                {
                    fr[time1]=gg;
                    ansr[time1]=i;
                }
            }
            what_to_check[i].clear();
        }
        //cout<<"??3\n";
        new_llervals.clear();
        for(auto xd:llervals)
        {
            ll mid=(xd.first+xd.second)/2;
            if(xd.first==xd.second)continue;
            if(xd.first<=mid-1)new_llervals.push_back({xd.first,mid-1});
            if(mid+1<=xd.second)new_llervals.push_back({mid+1,xd.second});
        }
        llervals=new_llervals;
    }
}
void compute_left(ll factor)
{
    ll max_time=(start1-1)*factor+start1;
    vector<pair<ll,ll> >llervals;
    vector<pair<ll,ll> >new_llervals;
    llervals.push_back({0,max_time});
    for(;llervals.size()>0;)
    {
        //memset(what_to_check,-1,sizeof(what_to_check));
        for(auto xd:llervals)
        {
            ll mid=(xd.first+xd.second)/2;
            if(xd.second+1<=max_time)low[mid]=ansl[xd.second+1];
            else low[mid]=1;
            if(xd.first-1>=0)high[mid]=ansl[xd.first-1];
            else high[mid]=start1;
            //cout<<"aloo  "<<mid<<" "<<low[mid]<<" "<<high[mid]<<endl;
            for(ll j=low[mid];j<=high[mid];j++)
            {
                what_to_check[j].push_back(mid);
            }
        }
        tr.init();
        for(ll i=start1;i>=1;i--)
        {
            tr.update(1,n1,1,num[i],att[i]);
            for(auto time1:what_to_check[i])
            {
                if(time1==-1)continue;
                //cout<<"%% "<<i<<" "<<time1<<endl;
                //cout<<time1-(start1-i)*factor<<endl;
                ll gg=tr.query(1,n1,1,time1-(start1-i)*factor);
                //cout<<"update left"<<time1<<" "<<gg<<endl;
                if(gg>fl[time1])
                {
                    fl[time1]=gg;
                    ansl[time1]=i;
                }
            }
            what_to_check[i].clear();
        }
        new_llervals.clear();
        for(auto xd:llervals)
        {
            ll mid=(xd.first+xd.second)/2;
            //cout<<"^^ "<<mid<<" "<<fl[mid]<<" "<<ansl[mid]<<endl;
            if(xd.first==xd.second)continue;
            if(xd.first<=mid-1)new_llervals.push_back({xd.first,mid-1});
            if(mid+1<=xd.second)new_llervals.push_back({mid+1,xd.second});
        }
        llervals=new_llervals;
    }
}
ll solve_right()
{
    memset(fl,-1,sizeof(fl));
    memset(fr,-1,sizeof(fr));
    compute_right(2);
    compute_left(1);
    ll ret=0;
    ll mx=0;
    for(ll t1=d1;t1>=0;t1--)
    {
        if(d1-t1<0)continue;
        mx=max(mx,fr[d1-t1]);
        if(fl[t1]<0)continue;
        //if(fr[d1-t1]<0)continue;
        //cout<<t1<<" "<<fl[t1]<<" "<<mx<<endl;
        ret=max(ret,fl[t1]+mx);
        //cout<<t1<<" "<<fl[t1]<<" "<<fr[d1-t1]<<endl;
    }
    return ret;
}
ll solve_left()
{
    memset(fl,-1,sizeof(fl));
    memset(fr,-1,sizeof(fr));
    compute_right(1);
    compute_left(2);
    ll ret=0,mx=0;
    for(ll t1=d1;t1>=0;t1--)
    {
        if(d1-t1<0)continue;
        mx=max(mx,fr[d1-t1]);
        if(fl[t1]<0)continue;
        //if(fr[d1-t1]<0)continue;
        ret=max(ret,fl[t1]+mx);
        //cout<<t1<<" "<<fl[t1]<<" "<<mx<<endl;
    }
    return ret;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<pair<ll,ll> >by_value;
    for(ll i=0;i<n;i++)
    {
        att[i+1]=attraction[i];
        by_value.push_back({att[i+1],i+1});
    }
    sort(by_value.begin(),by_value.end());
    for(ll i=0;i<by_value.size();i++)
    {
        num[by_value[i].second]=i+1;
    }
    n1=n;start1=start;d1=d;
    start1++;
    return max(solve_left(), solve_right());
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:214:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |     for(ll i=0;i<by_value.size();i++)
      |                ~^~~~~~~~~~~~~~~~

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