Submission #907141

#	Time	Username	Problem	Language	Result	Execution time	Memory
907141		MilosMilutinovic	Two Dishes (JOI19_dishes)	C++14	10 / 100	10091 ms	70092 KiB

dishes

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,a[1000005],p[1000005],b[1000005],q[1000005];
ll s[1000005],t[1000005],pa[1000005],pb[1000005],mx[4000005],inc[4000005],val[4000005],dp[1000005];
bool tag[4000005];
vector<pii> qs[1000005];

void pushdown(int id){
	if(tag[id]){
		mx[id<<1]=val[id];
		mx[id<<1|1]=val[id];
		val[id<<1]=val[id];
		val[id<<1|1]=val[id];
		inc[id<<1]=0;
		inc[id<<1|1]=0;
		tag[id<<1]=true;
		tag[id<<1|1]=true;
		inc[id]=0;
		tag[id]=false;
	}else{
		mx[id<<1]+=inc[id];
		mx[id<<1|1]+=inc[id];
		inc[id<<1]+=inc[id];
		inc[id<<1|1]+=inc[id];
		val[id<<1]+=inc[id];
		val[id<<1|1]+=inc[id];
		inc[id]=0;
	}
}

void rangeadd(int id,int l,int r,int ql,int qr,ll v){
	if(ql<=l&&r<=qr){
		mx[id]+=v;
		inc[id]+=v;
		val[id]+=v;
		pushdown(id);
		return;
	}
	pushdown(id);
	int mid=(l+r)/2;
	if(qr<=mid) rangeadd(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) rangeadd(id<<1|1,mid+1,r,ql,qr,v);
	else rangeadd(id<<1,l,mid,ql,qr,v),rangeadd(id<<1|1,mid+1,r,ql,qr,v);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
}

void rangeset(int id,int l,int r,int ql,int qr,ll v){
	if(ql<=l&&r<=qr){
		mx[id]=v;
		val[id]=v;
		tag[id]=true;
		inc[id]=0;
		pushdown(id);
		return;
	}
	pushdown(id);
	int mid=(l+r)/2;
	if(qr<=mid) rangeset(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) rangeset(id<<1|1,mid+1,r,ql,qr,v);
	else rangeset(id<<1,l,mid,ql,qr,v),rangeset(id<<1|1,mid+1,r,ql,qr,v);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
}

ll query(int id,int l,int r,int qi){
	if(l==r) return mx[id];
	pushdown(id);
	int mid=(l+r)/2;
	ll ret=0;
	if(qi<=mid) ret=query(id<<1,l,mid,qi);
	else ret=query(id<<1|1,mid+1,r,qi);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
	return ret;
}

int main() {
	n=readint(); m=readint();
	for(int i=1;i<=n;i++){
		a[i]=readint();
		s[i]=readint();
		p[i]=readint();
	}
	for(int i=1;i<=m;i++){
		b[i]=readint();
		t[i]=readint();
		q[i]=readint();
	}
	for(int i=1;i<=n;i++) pa[i]=pa[i-1]+a[i];
	for(int i=1;i<=m;i++) pb[i]=pb[i-1]+b[i];
	for(int i=1;i<=n;i++){
		if(s[i]<pa[i]) continue;
		int l=1,r=m,pos=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(pa[i]+pb[mid]<=s[i]) pos=mid,l=mid+1;
			else r=mid-1;
		}
		qs[i].pb(mp(pos,p[i]));
	}
	ll res=0;
	for(int i=1;i<=m;i++){
		if(t[i]<pb[i]) continue;
		int l=1,r=n,pos=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(pa[mid]+pb[i]<=t[i]) pos=mid,l=mid+1;
			else r=mid-1;
		}
		res+=q[i];
		qs[pos+1].pb(mp(i-1,-q[i]));
	}
	for(int i=0;i<=n;i++){
		sort(qs[i].begin(),qs[i].end());
		/* vector<int> xs(1,m);
		for(auto&p:qs[i]){
			rangeadd(1,0,m,0,p.first,p.second);
			xs.push_back(p.first);
		}
		sort(xs.begin(),xs.end());
		xs.erase(unique(xs.begin(),xs.end()),xs.end());
		for(int j=1;j<(int)xs.size();j++){
			ll vl=query(1,0,m,xs[j-1]);
			ll vr=query(1,0,m,xs[j]);
			if(vl>vr) rangeset(1,0,m,xs[j-1],xs[j],vl);
		} */
		for(auto&p:qs[i]){
			for(int j=0;j<=p.first;j++) dp[j]+=p.second;
		}
		for(int j=1;j<=m;j++) dp[j]=max(dp[j-1],dp[j]);
	}
	printf("%lld\n",dp[m]+res);
	return 0;
}

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