Submission #1294417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294417		trandangquang	Two Dishes (JOI19_dishes)	C++20	100 / 100	2178 ms	222148 KiB

dishes

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=1e6+5;

int n,m; ll a[N],s[N],p[N],b[N],t[N],q[N],pa[N],pb[N],x[N],y[N],res;
vector<pair<int,ll>> que[N];

void solve(){
    cin>>n>>m;
    foru(i,1,n) cin>>a[i]>>s[i]>>p[i], pa[i]=pa[i-1]+a[i];
    foru(i,1,m) cin>>b[i]>>t[i]>>q[i], pb[i]=pb[i-1]+b[i];

    foru(i,1,n){
        x[i]=upper_bound(pb,pb+1+m,s[i]-pa[i])-pb-1;
        if(x[i]<0) continue;
        que[i].eb(x[i],p[i]);
    }
    foru(i,1,m){
        y[i]=upper_bound(pa,pa+1+n,t[i]-pb[i])-pa-1;
        if(y[i]<0) continue;
        res+=q[i];
        if(y[i]<n) que[y[i]+1].eb(i-1,-q[i]);
    }

    map<int, ll> diff;
    foru(i,0,n){
        sort(all(que[i]));

        for(auto [pos,val]:que[i]){
            diff[0]+=val;
            diff[pos+1]-=val;
        }

        for(auto [pos,val]:que[i]){
            auto it=diff.upper_bound(pos);
            while(it!=diff.end() && it->fi<=m && it->se<0){
                auto jt=next(it);
                if(jt!=diff.end()){
                    jt->se+=it->se;
                }
                it=diff.erase(it);
            }
        }
    }

    foru(i,0,m) res+=diff[i];
    cout<<res<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    foru(i,1,tc){
        solve();
    }
}

Compilation message (stderr)

dishes.cpp: In function 'int32_t main()':
dishes.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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