제출 #1015243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015243		amirhoseinfar1385	휴가 (IOI14_holiday)	C++17	0 / 100	108 ms	8132 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=19,kaf=(1<<lg);
long long all[maxn],n,st,k,allind[maxn];
long long mainres=0;
struct segment{
    long long seg[(1<<(lg+1))];
    void upd(long long i,long long w){
        i+=kaf;
        while(i>0){
            seg[i]+=w;
            i>>=1;
        }
        return ;
    }
    long long pors(long long i,long long l,long long r,long long tl,long long tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return 0;
        }
        if(l>=tl&&r<=tr){
            return seg[i];
        }
        long long m=(l+r)>>1;
        return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
    }
    long long porsakh(long long i,long long l,long long r,long long w){
        if(l>r||seg[i]<w){
            return -1;
        }
        if(l==r){
            return l;
        }
        long long m=(l+r)>>1;
        if(seg[(i<<1)^1]>=w){
            return porsakh((i<<1)^1,m+1,r,w);
        }
        return porsakh((i<<1),l,m,w-seg[(i<<1)^1]);
    }
}seg1,seg2;

void ins(int l,int r,int w){
    for(int i=l;i<=r;i++){
        seg1.upd(allind[i],w*all[i]);
        seg2.upd(allind[i],w);
    }
}

void solve(long long l,long long r,long long tl,long long tr){
    if(l>r){
        return ;
    }
    long long mid=(l+r)>>1,opt=tl,mx=-1;
    ins(max(l,tr+1),mid,1);
    for(long long i=tr;i>=tl;i--){
        seg2.upd(allind[i],1);
        seg1.upd(allind[i],all[i]);
        long long ted=k-(mid-i+min(mid-st,st-i));
        long long z=seg2.porsakh(1,0,kaf-1,ted);
        long long fake=seg1.pors(1,0,kaf-1,z,n+1);
        if(fake>mx){
            mx=fake;
            opt=i;
        }
    }
    for(long long i=l;i<=mid;i++){
        seg1.upd(allind[i],-all[i]);
        seg2.upd(allind[i],-1);
    }
    for(long long i=tr;i>=tl;i--){
        seg2.upd(allind[i],-1);
        seg1.upd(allind[i],-all[i]);
    }
    mainres=max(mainres,mx);

    for(long long i=opt+1;i<=tr;i++){
        seg1.upd(allind[i],all[i]);
        seg2.upd(allind[i],1);
    }

    solve(l,mid-1,tl,opt);

    for(long long i=opt+1;i<=tr;i++){
        seg1.upd(allind[i],-all[i]);
        seg2.upd(allind[i],-1);
    }

    for(long long i=l;i<=mid;i++){
        seg1.upd(allind[i],all[i]);
        seg2.upd(allind[i],1);
    }
    solve(mid+1,r,opt,tr);
    for(long long i=l;i<=mid;i++){
        seg1.upd(allind[i],-all[i]);
        seg2.upd(allind[i],-1);
    }
}

long long findMaxAttraction(int N,int start,int d,int attraction[]) {
    n=N;
    st=start;
    k=d;
    st++;
    vector<pair<long long ,long long>>comper;
    for(long long i=1;i<=n;i++){
        all[i]=attraction[i-1];
        comper.push_back(make_pair(all[i],i));
    }
    sort(comper.begin(),comper.end());
    comper.resize(unique(comper.begin(),comper.end())-comper.begin());
    for(long long i=1;i<=n;i++){
        allind[i]=lower_bound(comper.begin(),comper.end(),make_pair(all[i],i))-comper.begin();
    }
    solve(st,n,1,st);
    return mainres;
}

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