제출 #384183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384183		kshitij_sodani	Holiday (IOI14_holiday)	C++14	47 / 100	461 ms	65540 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
#define mp make_pair
typedef long long llo;

#include"holiday.h"

llo it[100001];
llo n;

llo d;
llo ans=0;
llo ii;
llo tree[100000*40][2];
llo ll[100000*40][2];
llo rr[100000*40][2];
llo ind[1000001];
llo co[2];
llo cur[2];

vector<llo> rr3;
vector<llo> rr2;

llo update(llo no,llo l,llo r,llo i,llo val,llo tt){
    llo ac=co[tt];
    co[tt]++;
    tree[ac][tt]=tree[no][tt];
    ll[ac][tt]=ll[no][tt];
    rr[ac][tt]=rr[no][tt];
    if(l==r){
        tree[ac][tt]+=val;
        return ac;
    }
    else{
        llo mid=(l+r)/2;
        if(i<=mid){
            ll[ac][tt]=update(ll[ac][tt],l,mid,i,val,tt);
        }
        else{
            rr[ac][tt]=update(rr[ac][tt],mid+1,r,i,val,tt);
        }
        tree[ac][tt]=tree[ll[ac][tt]][tt]+tree[rr[ac][tt]][tt];
        return ac;
    }

}
llo xy=0;
llo query(llo no,llo no2,llo l,llo r,llo k){
  /*  if(xy){
        cout<<no<<",,"<<no2<<",,"<<l<<",,"<<r<<",,"<<k<<endl;
    }*/
    if(l==r){
        
        
        return l;
        //if(tree[no2]-tree[no]==)
    }
    else{
        llo mid=(l+r)/2;
        if(tree[ll[no2][0]][0]-tree[ll[no][0]][0]<k){
            return query(rr[no][0],rr[no2][0],mid+1,r,k-(tree[ll[no2][0]][0]-tree[ll[no][0]][0]));
        }
        else{
            return query(ll[no][0],ll[no2][0],l,mid,k);
        }
    }
}


llo query2(llo no,llo l,llo r,llo aa,llo bb){
    if(r<aa or l>bb){
        return 0;
    }
    if(aa<=l and r<=bb){


        return tree[no][1];
    }
    else{
        llo mid=(l+r)/2;
        return query2(ll[no][1],l,mid,aa,bb)+query2(rr[no][1],mid+1,r,aa,bb);
    }
}
void solve(llo l,llo r,llo aa,llo bb){
    llo mid=(l+r)/2;
    pair<llo,llo> cur={0,aa};
    for(llo x=aa;x<=bb;x++){
        llo le=d-2*(ii-mid)-(x-ii);
        //mid to x range
        if(le>0){
            llo zz;
           /* if(mid==1 and x==4){
                xy=1;
                cout<<le<<")"<<endl;
            }*/
           /* vector<llo> xx2;
            for(llo k=mid;k<=x;k++){
                xx2.pb(it[k]);
            }
            sort(xx2.begin(),xx2.end());
*/
            llo su=0;
           /* for(llo i=0;i<xx2.size();i++){
                if(i+1>le){
                    break;
                }
                su+=xx2[i];
            }*/
            if(le<x-mid+1){
                zz=query(rr3[mid],rr3[x+1],0,n-1,le);
            }
            else{
                zz=n-1;
            }
          //  xy=0;
          
            su=query2(rr2[zz+1],0,n-1,mid,x);
           /*  if(mid==1 and x==4){
                cout<<le<<")"<<zz<<"<"<<su<<endl;
            }*/

            if(su<cur.a){
                cur={su,x};
            }
        }
    }
   // cout<<mid<<":"<<cur.a<<":"<<cur.b<<endl;
    ans=min(ans,cur.a);
    if(mid>l){
        solve(l,mid-1,aa,cur.b);
    }
    if(mid<r){
        solve(mid+1,r,cur.b,bb);
    }
}

void solve(llo i){
    multiset<llo> ss;
    ii=i;

    llo su=0;
    for(llo j=i;j>=0;j--){
        if(i-j>d){
            break;
        }
        ss.insert(it[j]);
        su+=it[j];
        while(ss.size()>d-(i-j) and ss.size()>0){
            auto j=ss.end();
            j--;
            su-=(*j);
            ss.erase(j);
        }

        ans=min(ans,su);
    }
    if(i==0 or i==n-1){
        return;
    }
   /* for(llo j=0;j<n;j++){
        cout<<it[j]<<" ";
    }
    cout<<endl;
    cout<<i<<".."<<endl;*/
    vector<pair<llo,llo>> val;
    for(llo j=0;j<n;j++){
        val.pb({it[j],j});
    }
    sort(val.begin(),val.end());
    

    for(llo k=0;k<2;k++){
        co[k]=0;
        for(llo j=0;j<2*n;j++){
            tree[j][k]=0;
            ll[j][k]=j*2+1;
            rr[j][k]=j*2+2;
            co[k]=max(co[k],rr[j][k]+1);
        }
    }
    rr3.clear();
    rr2.clear();
    rr3.pb(0);
    cur[0]=0;
    cur[1]=0;
     for(llo j=0;j<n;j++){
        ind[val[j].b]=j;
    }
    for(llo j=0;j<n;j++){
        cur[0]=update(cur[0],0,n-1,ind[j],1,0);
        rr3.pb(cur[0]);
    }
    rr2.pb(0);
    for(llo j=0;j<n;j++){
        cur[1]=update(cur[1],0,n-1,val[j].b,val[j].a,1);
        rr2.pb(cur[1]);
      //  cout<<val[j].a<<"...."<<val[j].b<<endl;
    }   
   
    
    //return ;
    llo l=i;
    while(l>0){
        if((i-(l-1))*2<=d){
            l--;
        }
        else{
            break;
        }
    }
    if(i==0 or i==n-1){
        return;
    }
   // return ;
    solve(l,i,i,n-1);


}
 llo findMaxAttraction(int nn, int start, int dd, int at[]) {
    n=nn;
    d=dd;
    ans=0;
    for(llo i=0;i<n;i++){
    	it[i]=-at[i];
    }
    solve(start);
    for(llo i=0;i<n/2;i++){
    	swap(it[i],it[n-i-1]);
    }
    solve(n-start-1);


    return -ans;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'void solve(llo)':
holiday.cpp:151:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
  151 |         while(ss.size()>d-(i-j) and ss.size()>0){
      |               ~~~~~~~~~^~~~~~~~

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