Submission #1220268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220268		emptypringlescan	Two Dishes (JOI19_dishes)	C++17	74 / 100	3881 ms	293244 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
struct node{
	int s,e,m;
	node *l,*r;
	long long mx,lazya,lazys;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		mx=0; lazya=0; lazys=(long long)-1e18;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(s==e) return;
		if(lazys>=(long long)-1e18+5){
			l->mx=lazys;
			l->lazya=0;
			l->lazys=lazys;
			r->mx=lazys;
			r->lazya=0;
			r->lazys=lazys;
			lazys=-1e18;
		}
		if(lazya){
			l->mx+=lazya;
			l->lazya+=lazya;
			r->mx+=lazya;
			r->lazya+=lazya;
			lazya=0;
		}
	}
	void add(int S, int E, long long V){
		if(S<=s&&e<=E){
			mx+=V;
			lazya+=V;
			return;
		}
		prop();
		if(E<=m) l->add(S,E,V);
		else if(S>m) r->add(S,E,V);
		else l->add(S,m,V),r->add(m+1,E,V);
		mx=max(l->mx,r->mx);
	}
	void set(int S, int E, long long V){
		if(S<=s&&e<=E){
			mx=V;
			lazya=0;
			lazys=V;
			return;
		}
		prop();
		if(E<=m) l->set(S,E,V);
		else if(S>m) r->set(S,E,V);
		else l->set(S,m,V),r->set(m+1,E,V);
		mx=max(l->mx,r->mx);
	}
	int bsta(long long V){ //first pos bigger
		if(s==e){
			if(mx<=V) return s+1;
			else return s;
		}
		prop();
		if(l->mx>V) return l->bsta(V);
		else return r->bsta(V);
	}
	long long query(int S, int E){
		if(S<=s&&e<=E) return mx;
		prop();
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return max(l->query(S,m),r->query(m+1,E));
	}
} *root;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	pair<long long,pair<long long,long long> > arr[n],brr[m];
	long long pref=0,prefa[n+1],prefb[m+1];
	prefa[0]=prefb[0]=0;
	for(int i=0; i<n; i++){
		cin >> arr[i].first >> arr[i].second.first >> arr[i].second.second;
		pref+=arr[i].first;
		prefa[i+1]=prefa[i]+arr[i].first;
		arr[i].second.first-=pref;
	}
	pref=0;
	long long tota=0;
	for(int i=0; i<m; i++){
		cin >> brr[i].first >> brr[i].second.first >> brr[i].second.second;
		pref+=brr[i].first;
		prefb[i+1]=prefb[i]+brr[i].first;
		brr[i].second.first-=pref;
	}
	vector<pair<int,long long> > event[m+5];
	for(int i=0; i<n; i++){
		if(arr[i].second.first<0) continue;
		tota+=arr[i].second.second;
		int ind=upper_bound(prefb,prefb+m+1,arr[i].second.first)-prefb-1;
		event[ind].push_back({i,-arr[i].second.second});
	}
	for(int i=0; i<m; i++){
		if(brr[i].second.first<0) continue;
		int ind=upper_bound(prefa,prefa+n+1,brr[i].second.first)-prefa-1;
		event[i].push_back({ind,brr[i].second.second});
	}/*
	for(int i=0; i<=m; i++){
		cout << i << ":\n";
		for(auto j:event[i]) cout << j.first << ' ' << j.second << '\n';
	}*/
	root=new node(0,n);
	for(int i=0; i<=m; i++){
		for(auto j:event[i]){
			if(j.second<=0){
				root->add(0,j.first,j.second);
			}
			else{
				long long x=root->query(0,j.first);
				int ind=root->bsta(x+j.second);
				assert(ind>j.first);
				root->add(0,j.first,j.second);
				root->set(j.first,ind-1,x+j.second);
			}
		}
	}
	cout << root->mx+tota;
}

• 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: 0 / 17
• Subtask 8: 0 / 9