Submission #1284608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284608		user736482	Tricks of the Trade (CEOI23_trade)	C++20	55 / 100	1974 ms	454984 KiB

trade

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<31)
#define DUZO 20000000LL
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
ll n,k,a,ak=1;
vi v1,v2;
ll il[DUZO],lw[DUZO],pw[DUZO],sm[DUZO];
ll rt[250007];
ll dod(ll v,ll tg,ll pocz,ll kon){
    if(pocz>tg || kon<tg)return v;
    if(pocz==kon){
        il[ak]=il[v]+1;
        sm[ak]=sm[v]+tg;
        return ak++;
    }
    ll x=ak++;
    lw[x]=dod(lw[v],tg,pocz,(pocz+kon)/2);
    pw[x]=dod(pw[v],tg,(pocz+kon)/2+1,kon);
    il[x]=il[lw[x]]+il[pw[x]];
    sm[x]=sm[lw[x]]+sm[pw[x]];
    return x;
}
ll s(ll v1,ll v2,ll m,ll l,ll r){
    if(!m)return 0;
    if(l==r)return m*l;
    if(il[pw[v2]]-il[pw[v1]]<=m){  
        m-=(il[pw[v2]]-il[pw[v1]]);
        return sm[pw[v2]]-sm[pw[v1]]+s(lw[v1],lw[v2],m,l,(l+r)/2);
    }
    return s(pw[v1],pw[v2],m,(l+r)/2+1,r);
}
ll vl(ll v1,ll v2,ll m,ll l,ll r){
    if(!m)return 0;
    if(l==r)return l;
    if(il[pw[v2]]-il[pw[v1]]<m){  
        m-=(il[pw[v2]]-il[pw[v1]]);
        return vl(lw[v1],lw[v2],m,l,(l+r)/2);
    }
    return vl(pw[v1],pw[v2],m,(l+r)/2+1,r);
}
vi pref={0};
ll val(ll l,ll r){
    if(r-l+1<k)return -INFL;
    return pref[l]-pref[r+1]+s(rt[l],rt[r+1],k,1,POT/2);
}
pii opt[250007],opt2[250007];  
void slv(ll l,ll r,ll lo,ll ro){
    if(l>r)return;
    pii bs={-INFL,1};
    ll md=(l+r)/2;
    for(ll i=lo;i<=ro;i++)bs=max(bs,{val(md,i),-i});
    opt[md]={bs.ff,-bs.ss};
    if(bs.ff==-INFL)opt[md].ss=ro;
    slv(l,md-1,lo,opt[md].ss);
    slv(md+1,r,opt[md].ss,ro);
}
void slv2(ll l,ll r,ll lo,ll ro){
    if(l>r)return;
    pii bs={-INFL,-1};
    ll md=(l+r)/2;
    for(ll i=lo;i<=ro;i++)bs=max(bs,{val(i,md),i});
    opt2[md]={bs.ff,bs.ss};
    if(bs.ff==-INFL)opt2[md].ss=lo;
    slv2(l,md-1,lo,opt2[md].ss);
    slv2(md+1,r,opt2[md].ss,ro);
}
#define PT2 (1<<19)
ll mn[PT2];
void up(ll v,ll l,ll r,ll pocz,ll kon,ll x){
    if(l>kon || r<pocz)return;
    if(l>=pocz && r<=kon)mn[v]=min(mn[v],x);
    else{
        up(v*2,l,(l+r)/2,pocz,kon,x);
        up(v*2+1,(l+r)/2+1,r,pocz,kon,x);
    }
}
ll mnn(ll v){
    v+=PT2/2;
    ll a=INFL;
    while(v){
        a=min(a,mn[v]);
        v/=2;
    }
    return a;
}
void solve(){
    for(ll i=0;i<PT2;i++)mn[i]=INFL;
    cin>>n>>k;
    for(ll i=0;i<n;i++){
        cin>>a;
        v1.pb(a);
        pref.pb(pref.back()+a);
    }
    for(ll i=0;i<n;i++){
        cin>>a;
        v2.pb(a);
    }
    for(ll i=0;i<DUZO;i++)lw[i]=pw[i]=DUZO-1;
    for(ll i=1;i<=n;i++){
        rt[i]=dod(rt[i-1],v2[i-1],1,POT/2);
    }
    slv(0,n-1,0,n-1);
    slv2(0,n-1,0,n-1);
    ll mx=-INFL;
    for(ll i=0;i<n;i++)mx=max(mx,opt2[i].ff);
    cout<<mx<<"\n"<<flush;
    for(ll i=0;i<n;i++){
        if(opt[i].ff==mx)up(1,1,PT2/2,i+1,opt[i].ss+1,vl(rt[i],rt[opt[i].ss+1],k,1,POT/2));
        if(opt2[i].ff==mx)up(1,1,PT2/2,opt2[i].ss+1,i+1,vl(rt[opt2[i].ss],rt[i+1],k,1,POT/2));
    }
    for(ll i=0;i<n;i++){
        cout<<(mnn(i)<=v2[i]);
    }
    // ll q;
    // cin>>q;
    // for(ll i=0;i<q;i++){
    //     ll b,c;
    //     cin>>a>>b>>c;
    //     cout<<s(rt[a],rt[b+1],c,1,POT/2)<<" "<<vl(rt[a],rt[b+1],c,1,POT/2)<<"\n";
    // }

}                                                                   
int main(){
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}

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