제출 #384187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384187		kshitij_sodani	휴가 (IOI14_holiday)	C++14	100 / 100	2288 ms	13796 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*4][2];
llo ind[100001];
llo co[2];
llo cur[2];

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

void update(llo no,llo l,llo r,llo i,llo val,llo tt){
    tree[no][tt]+=val;
    if(l==r){

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

}
llo xy=0;
llo query(llo no,llo l,llo r,llo k){
    if(l==r){
        return l;
    }
    else{
        llo mid=(l+r)/2;
        if(tree[no*2+1][0]<k){
            return query(no*2+2,mid+1,r,k-tree[no*2+1][0]);
        }
        else{
            return query(no*2+1,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(no*2+1,l,mid,aa,bb)+query2(no*2+2,mid+1,r,aa,bb);
    }
}
void remove(int j){
    update(0,0,n-1,ind[j],-1,0);
    update(0,0,n-1,ind[j],-it[j],1);
}
void add(int j){
    update(0,0,n-1,ind[j],1,0);
    update(0,0,n-1,ind[j],it[j],1);
}
void solve(llo l,llo r,llo aa,llo bb,llo par=-1){

    llo mid=(l+r)/2;

    if(par==-1){
        for(int i=mid;i<=r;i++){
            add(i);
        }
    }
    pair<llo,llo> cur={0,aa};
    if(par!=-1){
        if(par<mid){
            for(int i=par;i<mid;i++){
                remove(i);
            }
        }
        else{
            for(int i=mid;i<par;i++){
                add(i);
            }
            for(int i=bb;i>aa;i--){
                remove(i);
            }
        }
    }
    remove(aa);
    for(llo x=aa;x<=bb;x++){
        add(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(0,0,n-1,le);
            }
            else{
                zz=n-1;
            }
          //  xy=0;
          
            su=query2(0,0,n-1,0,zz);
           /*  if(mid==1 and x==4){
                cout<<le<<")"<<zz<<"<"<<su<<endl;
            }*/

            if(su<cur.a){
                cur={su,x};
            }
        }
    }
    for(int j=cur.b+1;j<=bb;j++){
        remove(j);
    }
   // cout<<mid<<":"<<cur.a<<":"<<cur.b<<endl;



    ans=min(ans,cur.a);
    if(mid>l){
        solve(l,mid-1,aa,cur.b,mid);
    }
    if(mid<r){
        solve(mid+1,r,cur.b,bb,mid);
    }

    if(par!=-1){
        if(par<mid){
            for(int i=par;i<mid;i++){
                add(i);
            }
        }
        else{
            for(int i=mid;i<par;i++){
                remove(i);
            }
            for(int i=bb;i>aa;i--){
                add(i);
            }
        }
    }


    for(int j=cur.b;j>aa;j--){
        remove(j);
    }

}

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++){
        for(llo j=0;j<4*n;j++){
            tree[j][k]=0;
        }
    }
 /*   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:195: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]
  195 |         while(ss.size()>d-(i-j) and ss.size()>0){
      |               ~~~~~~~~~^~~~~~~~

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