Submission #971907

#	Time	Username	Problem	Language	Result	Execution time	Memory
971907		Warinchai	Holiday (IOI14_holiday)	C++14	24 / 100	220 ms	23808 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
//#define int long long
using namespace std;
long long rvid[100005];
struct segtree{
    long long info[400005];
    long long freq[400005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        //cerr<<"range:"<<st<<" "<<en<<"\n";
        if(st==en)return info[i]+=val,freq[i]++,void();
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
        freq[i]=freq[i*2]+freq[i*2+1];
    }
    void un_upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return info[i]-=val,freq[i]-=1,void();
        int m=(st+en)/2;
        un_upd(st,m,i*2,pos,val);
        un_upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
        freq[i]=freq[i*2]+freq[i*2+1];
    }
    long long fans(int st,int en,int i,long long pos){
        //cerr<<"Range:"<<st<<" "<<en<<"\n";
        if(st==en)return min(freq[i],pos)*(rvid[st]);
        int m=(st+en)/2;
        if(pos<=freq[i*2+1])return fans(m+1,en,i*2+1,pos);
        else return fans(st,m,i*2,pos-freq[i*2+1])+info[i*2+1];
    }
    void reset(int st,int en,int i){
        info[i]=0;
        freq[i]=0;
        if(st==en)return;
        int m=(st+en)/2;
        reset(st,m,i*2);
        reset(m+1,en,i*2+1);
    }
}tr;
vector<long long>v;
int id[100005];
long long dpl[100005];
long long dpr[100005];
int optl[100005];
int optr[100005];
map<int,int>mp;
struct query{
    int st,en,optl,optr;
    query(int a,int b,int c,int d){
        st=a,en=b,optl=c,optr=d;
    }
};
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    for(int i=0;i<n;i++)if(!mp[attraction[i]])v.push_back(attraction[i]),mp[attraction[i]]++;
    v.push_back(0);
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)rvid[i+1]=v[i];
    for(int i=0;i<n+1;i++)id[i]=lower_bound(v.begin(),v.end(),attraction[i])-v.begin()+1;
    long long ans=0;
    int cur=start;
    queue<pair<int,query>>q;
    q.push({1,query(0,d,start,n-1)});
    int cnt=0;
    int curlv=1;
    //cerr<<"work\n";
    while(!q.empty()){
        auto x=q.front().second;
        int lv=q.front().first;
        q.pop();
        if(x.st>x.en)continue;
        int m=(x.st+x.en)/2;
        //cerr<<"cur:"<<cur<<"\n";
        if(curlv<lv){
            curlv++;
            //cerr<<"reset\n";
            cnt+=n;
            tr.reset(1,n+1,1);
            cur=start;
        }
        //cerr<<x.optl<<" "<<x.optr<<"\n";
        while(cur<x.optl){
            cnt++;
            tr.upd(1,n+1,1,id[cur],attraction[cur]);
            cur++;
        }
        pair<long long,int>opt={-1ll,-1};
        for(int i=x.optl;i<=x.optr;i++){
            if(cur==i){
                cnt++;
                tr.upd(1,n+1,1,id[cur],attraction[cur]);
                cur++;
            }
            int left=m-abs(start-i);
            long long x=tr.fans(1,n+1,1,left);
            opt=max(opt,{x,i});
        }
        dpr[m]=opt.first;
        optr[m]=opt.second;
        //cerr<<x.st<<" "<<x.en<<" "<<m<<" "<<opt.first<<" "<<opt.second<<"\n";
        q.push({lv+1,query(x.st,m-1,x.optl,opt.second)});
        q.push({lv+1,query(m+1,x.en,opt.second,x.optr)});
    }
    //cerr<<"count:"<<cnt<<"\n";
    //cerr<<"work\n";
    //for(int i=0;i<=d;i++)cerr<<dpr[i]<<" ";
    //cerr<<"\n";
    tr.reset(1,n+1,1);
    cur=start;
    q.push({1,query(0,d,0,start)});
    //cerr<<"work\n";
    attraction[start]=0;
    id[start]=1;
    cnt=0;
    curlv=1;
    while(!q.empty()){
        auto x=q.front().second;
        int lv=q.front().first;
        q.pop();
        if(x.st>x.en)continue;
        int m=(x.st+x.en)/2;
        if(curlv<lv){
            curlv++;
            //cerr<<"reset\n";
            cnt+=n;
            tr.reset(1,n+1,1);
            cur=start;
        }
        //cerr<<x.optr<<" "<<x.optl<<"\n";
        while(cur>x.optr){
            cnt++;
            tr.upd(1,n+1,1,id[cur],attraction[cur]);
            cur--;
        }
        //cerr<<"cur:"<<cur<<"\n";
        pair<long long,int>opt={-1ll,-1};
        for(int i=x.optr;i>=x.optl;i--){
            if(cur==i){
                cnt++;
                tr.upd(1,n+1,1,id[cur],attraction[cur]);
                cur--;
            }
            int left=m-abs(start-i);
            long long x=tr.fans(1,n+1,1,left);
            opt=max(opt,{x,i});
        }
        dpl[m]=opt.first;
        optl[m]=opt.second;
        //cerr<<x.st<<" "<<x.en<<" "<<m<<" "<<opt.first<<" "<<opt.second<<" "<<x.optl<<" "<<x.optr<<"\n";
        q.push({lv+1,query(x.st,m-1,opt.second,x.optr)});
        q.push({lv+1,query(m+1,x.en,x.optl,opt.second)});
    }
    //cerr<<"count:"<<cnt<<"\n";
    //for(int i=0;i<=d;i++)cerr<<dpl[i]<<" ";
    //cerr<<"\n";
    for(int i=0;i<=d;i++){
        int left=d-i-abs(optr[i]-start);
        if(left<0)break;
        //cerr<<i<<" "<<left<<" "<<optr[i]<<" "<<dpr[i]+dpl[left]<<"\n";
        ans=max(ans,dpr[i]+dpl[left]);
    }
    for(int i=0;i<=d/2;i++){
        int left=d-i-abs(optl[i]-start);
        if(left<0)break;
        ans=max(ans,dpl[i]+dpr[left]);
    }
    return ans;
}

Compilation message (stderr)

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

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