Submission #731344

#	Time	Username	Problem	Language	Result	Execution time	Memory
731344		ogibogi2004	Holiday (IOI14_holiday)	C++14	0 / 100	235 ms	32596 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5e4+6;
const int INF=2e9;
int att[MAXN];
int low[MAXN],high[MAXN],n1,start1,d1;
priority_queue<int> pq;
int cur_sum;
int fr[MAXN],ansr[MAXN];
int fl[MAXN],ansl[MAXN];
//start1 will be in left
int what_to_check[MAXN];
struct node
{
    int cnt_cities;
    int sum;
};
struct segment_tree
{
    node tree[4*MAXN];
    void init()
    {
        for(int j=0;j<4*MAXN;j++)
        {
            tree[j].cnt_cities=0;
            tree[j].sum=0;
        }
    }
    void update(int l,int r,int idx,int pos,int val)
    {
        if(l>pos)return;
        if(r<pos)return;
        if(l==r)
        {
            tree[idx].cnt_cities=1;
            tree[idx].sum=val;
            return;
        }
        int 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;
    }
    int query(int l,int r,int idx,int 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;
        int 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;
int num[MAXN];
int compute_right(int factor)
{
    int max_time=(n1-start1)*factor+(n1-start1);
    vector<pair<int,int> >intervals;
    vector<pair<int,int> >new_intervals;
    intervals.push_back({0,max_time});
    for(;intervals.size()>0;)
    {
        memset(what_to_check,-1,sizeof(what_to_check));
        for(auto xd:intervals)
        {
            int 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;
            for(int j=low[mid];j<=high[mid];j++)
            {
                what_to_check[j]=mid;
            }
        }
        tr.init();
        for(int i=start1;i<=n1;i++)
        {
            if(i!=start1)tr.update(1,n1,1,num[i],att[i]);
            int time1=what_to_check[i];
            if(time1==-1)continue;
            int gg=tr.query(1,n1,1,time1-(i-start1)*factor);
            if(gg>fr[time1])
            {
                fr[time1]=gg;
                ansr[time1]=i;
            }
        }
        new_intervals.clear();
        for(auto xd:intervals)
        {
            int mid=(xd.first+xd.second)/2;
            if(xd.first==xd.second)continue;
            if(xd.first<=mid-1)new_intervals.push_back({xd.first,mid-1});
            if(mid+1<=xd.second)new_intervals.push_back({mid+1,xd.second});
        }
        intervals=new_intervals;
    }
}
int compute_left(int factor)
{
    int max_time=(start1-1)*factor+start1;
    vector<pair<int,int> >intervals;
    vector<pair<int,int> >new_intervals;
    intervals.push_back({0,max_time});
    for(;intervals.size()>0;)
    {
        memset(what_to_check,-1,sizeof(what_to_check));
        for(auto xd:intervals)
        {
            int mid=(xd.first+xd.second)/2;
            if(xd.first-1>=0)low[mid]=ansl[xd.second+1];
            else low[mid]=1;
            if(xd.second+1<=max_time)high[mid]=ansl[xd.first-1];
            else high[mid]=start1;
            for(int j=low[mid];j<=high[mid];j++)
            {
                what_to_check[j]=mid;
            }
        }
        tr.init();
        for(int i=start1;i>=1;i--)
        {
            tr.update(1,n1,1,num[i],att[i]);
            int time1=what_to_check[i];
            if(time1==-1)continue;
            //cout<<"%% "<<i<<" "<<time1<<endl;
            //cout<<time1-(start1-i)*factor<<endl;
            int gg=tr.query(1,n1,1,time1-(start1-i)*factor);
            if(gg>fl[time1])
            {
                fl[time1]=gg;
                ansl[time1]=i;
            }
        }
        new_intervals.clear();
        for(auto xd:intervals)
        {
            int 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_intervals.push_back({xd.first,mid-1});
            if(mid+1<=xd.second)new_intervals.push_back({mid+1,xd.second});
        }
        intervals=new_intervals;
    }
}
int solve_right()
{
    memset(fl,-1,sizeof(fl));
    memset(fr,-1,sizeof(fr));
    compute_right(2);
    compute_left(1);
    int ret=0;
    for(int t1=0;t1<MAXN;t1++)
    {
        if(fl[t1]<0)continue;
        if(fr[d1-t1]<0)continue;
        ret=max(ret,fl[t1]+fr[d1-t1]);
        //cout<<t1<<" "<<fl[t1]<<" "<<fr[d1-t1]<<endl;
    }
    return ret;
}
int solve_left()
{
    memset(fl,-1,sizeof(fl));
    memset(fr,-1,sizeof(fr));
    compute_right(1);
    compute_left(2);
    int ret=0;
    for(int t1=0;t1<MAXN;t1++)
    {
        if(fr[t1]<0)continue;
        if(fl[d1-t1]<0)continue;
        ret=max(ret,fr[t1]+fl[d1-t1]);
    }
    return ret;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<pair<int,int> >by_value;
    for(int 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(int 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 'int compute_right(int)':
holiday.cpp:102:1: warning: no return statement in function returning non-void [-Wreturn-type]
  102 | }
      | ^
holiday.cpp: In function 'int compute_left(int)':
holiday.cpp:150:1: warning: no return statement in function returning non-void [-Wreturn-type]
  150 | }
      | ^
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:190:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for(int i=0;i<by_value.size();i++)
      |                 ~^~~~~~~~~~~~~~~~

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