Submission #1171115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171115		user736482	Two Dishes (JOI19_dishes)	C++20	0 / 100	246 ms	36252 KiB

dishes

#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 998244353
#define POT 4194304
//#define POT 64
#define INF 1000000019
#define INFL 1000000000000000099LL
ll a,b,c,n,m;

ll sgtree[POT][3];//max, ile dod/na co set, typ operacji(2-set,1-add)

vector<pair<ll,pair<ll,ll>>>v1,v2;
vector<ll>pref1={0},pref2={0};
pair<ll,ll> kto[200007],kto2[200007];//ostatni ktory sprawia, ze sie licze   -2 to nigdy
vector<pair<ll,ll>> kogo[200007];

void spych(ll v){
    if(v>=POT/2)return;
    if(sgtree[v][2]==0)return;
    if(sgtree[v][2]==2){
        sgtree[v*2][0]=sgtree[v][1];
        sgtree[v*2][1]=sgtree[v][1];
        sgtree[v*2][2]=2;
        sgtree[v*2+1][0]=sgtree[v][1];
        sgtree[v*2+1][1]=sgtree[v][1];
        sgtree[v*2+1][2]=2;
        sgtree[v][1]=0;
        sgtree[v][2]=0;
    }
    else{
        sgtree[v*2][0]+=sgtree[v][1];
        sgtree[v*2][1]+=sgtree[v][1];

        sgtree[v*2+1][0]+=sgtree[v][1];
        sgtree[v*2+1][1]+=sgtree[v][1];
        if(sgtree[v*2][2]==0)
            sgtree[v*2][2]=1;
        if(sgtree[v*2][1]==0)
            sgtree[v*2][1]=1;
        sgtree[v][1]=0;
        sgtree[v][2]=0;
    }
}

void add(ll pocz,ll kon,ll l,ll r,ll v, ll val){
    
    if(pocz>r || kon<l){
        //cout<<pocz<<" "<<kon<<" "<<l<<" "<<r<<" "<<v<<" "<<val<<" "<<sgtree[v][0]<<"\n";
        return;}
    if(l>=pocz && r<=kon){
        if(sgtree[v][2]==0)
            sgtree[v][2]=1;
        sgtree[v][1]+=val;
        sgtree[v][0]+=val;
    }
    else{
        spych(v);
      //  cout<<pocz<<" "<<kon<<" "<<l<<" "<<r<<" "<<v<<" "<<val<<" "<<sgtree[v][0]<<"\n";
        add(pocz,kon,l,(l+r)/2,v*2,val);
        add(pocz,kon,(l+r)/2+1,r,v*2+1,val);
        sgtree[v][0]=max(sgtree[v*2][0],sgtree[v*2+1][0]);
    }
     //cout<<pocz<<" "<<kon<<" "<<l<<" "<<r<<" "<<v<<" "<<val<<" "<<sgtree[v][0]<<"\n";
}

void st(ll pocz,ll kon,ll l,ll r,ll v, ll val){
    if(pocz>r || kon<l)return;
    if(l>=pocz && r<=kon){
        sgtree[v][2]=2;
        sgtree[v][1]=val;
        sgtree[v][0]=val;
    }
    else{
        spych(v);
        st(pocz,kon,l,(l+r)/2,v*2,val);
        st(pocz,kon,(l+r)/2+1,r,v*2+1,val);
        sgtree[v][0]=max(sgtree[v*2][0],sgtree[v*2+1][0]);
    }
}
ll fnd(ll l,ll r,ll v, ll val){//pierwszy wiekszy
    if(l==r)return l;
    spych(v);
    if(sgtree[v*2][0]>val)return fnd(l,(l+r)/2,v*2,val);
    return fnd((l+r)/2+1,r,v*2+1,val);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>b>>a>>c;
        v1.pb({a,{b,c}});
        pref1.pb(pref1.back()+b);
    }
    for(ll i=0;i<m;i++){
        cin>>b>>a>>c;
        v2.pb({a,{b,c}});
        pref2.pb(pref2.back()+b);
    }
    for(ll i=0;i<n;i++){
        ll pocz=-2;
        ll kon=m-1;
        while(pocz!=kon){
            ll mid=(pocz+kon+1)/2;
            if(pref1[i+1]+pref2[mid+1]<=v1[i].ff){
                pocz=mid;
            }
            else{
                kon=mid-1;
            }
        }
        kto[i+1]={pocz,v1[i].ss.ss};
    }
    for(ll i=0;i<m;i++){
        ll pocz=-2;
        ll kon=n-1;
        while(pocz!=kon){
            ll mid=(pocz+kon+1)/2;
            if(pref2[i+1]+pref1[mid+1]<=v2[i].ff){
                pocz=mid;
            }
            else{
                kon=mid-1;
            }
        }
        //cout<<i<<" "<<pocz<<"\n";
    //    kto2[i]=pocz;
        if(pocz>-2){
            kogo[pocz+1].pb({i,v2[i].ss.ss});
        }
        else{
         //    cout<<i<<" ";
        }
    }
    for(ll i=0;i<=n;i++){
     //  cout<<kto[i].ff<<" "<<kto[i].ss<<"\n\n";
        if(kto[i].ff!=-2){
        add(1,kto[i].ff+2,1,POT/2,1,kto[i].ss);
        if(kto[i].ss>0){
            ll pom=POT/2+kto[i].ff+1;
            vector<ll>vpom;
            while(pom){
                vpom.pb(pom);
                pom/=2;
            }
            while(vpom.size()){
                spych(vpom.back());
                vpom.pop_back();
            }
            pom=sgtree[POT/2+kto[i].ff+1][0];
            ll pom2=fnd(1,POT/2,1,pom);
           // cout<<pom<<" "<<pom2<<"\n";
            st(kto[i].ff+1,pom2-1,1,POT/2,1,pom);
        }}
        //cout<<sgtree[1][0]<<"    ";
        for(pair<ll,ll>j :kogo[i]){
            
          //  cout<<j.ff<<" "<<j.ss<<"x\n";
            add(1,POT/2,1,POT/2,1,j.ss);
        //       cout<<sgtree[1][0]<<"    ";
            add(1,j.ff+1,1,POT/2,1,-j.ss);
            if(j.ss<0 && j.ff){
                ll pom=POT/2+j.ff;
                vector<ll>vpom;
                while(pom){
                    vpom.pb(pom);
                    pom/=2;
                }
                while(vpom.size()){
                    spych(vpom.back());
                    vpom.pop_back();
                }
                pom=sgtree[POT/2+j.ff][0];
                ll pom2=fnd(1,POT/2,1,pom);
                st(j.ff+1,pom2-1,1,POT/2,1,pom);
            }
           // cout<<sgtree[1][0]<<"    ";
        }
       // cout<<sgtree[1][0]<<"   ";
       // cout<<"\n\n";
    }
    cout<<sgtree[1][0];

}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9