제출 #1164152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164152		imarn	Tricks of the Trade (CEOI23_trade)	C++20	100 / 100	1910 ms	264736 KiB

trade

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=3e5+5;
ll c[mxn]{0},s[mxn]{0};
vector<ll>vs;
int nn,n,k;
vector<pii>rs;
struct node{
    int tt;ll sm;
    node*l,*r;
    node() : tt(0),sm(0),l(0),r(0){};
    node(ll x) : tt(1),sm(x),l(0),r(0){};
    node(ll x,int y) : tt(y),sm(x),l(0),r(0){};
    node(node*tl,node*tr) : tt(tl->tt+tr->tt),sm(tl->sm+tr->sm),l(tl),r(tr){};
};
node *build(int l,int r){
    if(l==r)return new node();
    int m=(l+r)>>1;
    return new node(build(l,m),build(m+1,r));
}node*rt[mxn];
node *update(node *t,int l,int r,int idx,ll v){
    if(l==r)return new node(t->sm+v,t->tt+1);
    int m=(l+r)>>1;
    if(idx<=m)return new node(update(t->l,l,m,idx,v),t->r);
    return new node(t->l,update(t->r,m+1,r,idx,v));
}
ll qr(node *tl,node *tr,int l,int r,int k){
    if(l==r){
        return min(tr->sm-tl->sm,vs[l-1]*k);
    }int m=(l+r)>>1;
    int te=tr->r->tt-tl->r->tt;
    if(te>=k)return qr(tl->r,tr->r,m+1,r,k);
    return tr->r->sm-tl->r->sm+qr(tl->l,tr->l,l,m,k-te);
}
int qr2(node *tl,node*tr,int l,int r,ll v){
    if(l==r)return 1;
    int m=(l+r)>>1;
    if(v<=vs[m-1])return qr2(tl->l,tr->l,l,m,v)+tr->r->tt-tl->r->tt;
    else return qr2(tl->r,tr->r,m+1,r,v);
}
ll ans=-1e16;
void solve(int l,int r,int opl,int opr){
    if(r<l)return;
    int m=(l+r)>>1;
    pll t={-1e16,-1};
    for(int i=opl;i<=min(m-k+1,opr);i++){
        ll rsq=-c[m]+c[i-1]+s[m]+qr(rt[i-1],rt[m-1],1,nn,k-1);
        t=max(t,{rsq,i});
        if(ans==rsq)rs.pb({i,m});
        else if(ans<rsq){rs.clear();rs.pb({i,m});ans=rsq;}
    }if(t.s!=-1)solve(l,m-1,opl,t.s);
    else solve(l,m-1,opl,opr);
    if(t.s!=-1)solve(m+1,r,t.s,opr);
    else solve(m+1,r,opl,opr);
}
void solve2(int l,int r,int opl,int opr){
    if(r<l)return;
    int m=(l+r)>>1;
    pll t={-1e16,1};
    for(int i=opl;i<=min(m-k+1,opr);i++){
        ll rsq=-c[m]+c[i-1]+s[m]+qr(rt[i-1],rt[m-1],1,nn,k-1);
        t=max(t,{rsq,-i});
        if(ans==rsq)rs.pb({i,m});
        else if(ans<rsq){rs.clear();rs.pb({i,m});ans=rsq;}
    }if(-t.s!=-1)solve2(l,m-1,opl,-t.s);
    else solve2(l,m-1,opl,opr);
    if(-t.s!=-1)solve2(m+1,r,-t.s,opr);
    else solve2(m+1,r,opl,opr);
}
bool vis[mxn]{0};
pll t[2*mxn];
void del(int i,int sz){
    i+=sz;t[i]={-1e12,-1};
    for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
}
pll query(int l,int r,int sz,pll rs={-1e12,-1}){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=max(rs,t[l++]);
        if(r&1)rs=max(rs,t[--r]);
    }return rs;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;for(int i=1;i<=n;i++)cin>>c[i],c[i]+=c[i-1];for(int i=1;i<=n;i++)cin>>s[i],vs.pb(s[i]);
    sort(all(vs));vs.erase(unique(all(vs)),vs.end());nn=sz(vs);
    rt[0]=build(1,nn);
    for(int i=0;i<n;i++)t[i+n]={s[i+1],i+1};
    for(int i=n-1;i>0;i--)t[i]=max(t[2*i],t[2*i+1]);
    for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,nn,ub(vs,s[i]),s[i]);
    solve(1,n,1,n);solve2(1,n,1,n);
    for(auto [l,r] : rs){
        //cout<<l<<' '<<r<<'\n';
        while(1){
            pll vx=query(l-1,r,n);
            if(vx.f==-1e12)break;
            int x=qr2(rt[l-1],rt[r],1,nn,s[vx.s]);
            if(x>k)break;
            vis[vx.s]=1;
            del(vx.s-1,n);
        }
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)cout<<vis[i];
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45