제출 #1370579

#제출 시각아이디문제언어결과실행 시간메모리
1370579PieArmyTwo Dishes (JOI19_dishes)C++20
100 / 100
3607 ms215044 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

const ll inf=1e18;

struct Seg{
	int n;
	vector<ll>tree,add,lazy;
	void init(int N){
		n=N;
		tree.resize(n<<2,0);
		add.resize(n<<2,0);
		lazy.resize(n<<2,inf);
	}
	void push(int node,int left,int right){
		if(lazy[node]!=inf)tree[node]=lazy[node];
		tree[node]+=add[node];
		if(left!=right){
			if(lazy[node]!=inf){
				add[node*2]=0;
				lazy[node*2]=lazy[node];
				add[node*2+1]=0;
				lazy[node*2+1]=lazy[node];
			}
			add[node*2]+=add[node];
			add[node*2+1]+=add[node];
		}
		lazy[node]=inf;
		add[node]=0;
	}
	ll l,r,x;
	void rans(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r){
			add[node]=0;
			lazy[node]=x;
			push(node,left,right);
			return;
		}
		push(node,left,right);
		if(left>r||right<l)return;
		rans(node*2,left,mid);
		rans(node*2+1,mid+1,right);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void rangeset(int left,int right,ll val){
		l=left;r=right;x=val;
		if(l>r)return;
		rans();
	}
	void rana(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r){
			add[node]+=x;
			push(node,left,right);
			return;
		}
		push(node,left,right);
		if(left>r||right<l)return;
		rana(node*2,left,mid);
		rana(node*2+1,mid+1,right);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void rangeadd(int left,int right,ll val){
		l=left;r=right;x=val;
		if(l>r)return;
		rana();
	}
	ll qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return -inf;
		push(node,left,right);
		if(left>=l&&right<=r)return tree[node];
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	ll query(int left,int right){
		l=left;r=right;
		if(l>r)return -inf;
		return qu();
	}
	int walk(ll x,int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		push(node,left,right);
		if(tree[node]<=x)return n;
		if(left==right)return left;
		int res=walk(x,node*2,left,mid);
		if(res!=n)return res;
		return walk(x,node*2+1,mid+1,right);
	}
};

int n,m;
vector<pair<int,ll>>v[1000023];
ll arr[1000023],brr[1000023];
ll sa[1000023],sb[1000023];
int ca[1000023],cb[1000023];
ll ans=0;
Seg seg;

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>arr[i]>>sa[i]>>ca[i];
		arr[i]+=arr[i-1];
	}
	for(int i=1;i<=m;i++){
		cin>>brr[i]>>sb[i]>>cb[i];
		brr[i]+=brr[i-1];
	}
	for(int i=1;i<=n;i++){
		int l=0,r=m+1;
		while(l<r){
			int mi=(l+r)/2;
			if(brr[mi]+arr[i]>sa[i])r=mi;
			else l=mi+1;
		}
		if(l==m+1){
			ans+=ca[i];
		}
		else if(l){
			v[i].pb({l,ca[i]});
		}
	}
	//cerr<<endl;
	for(int i=1;i<=m;i++){
		int l=0,r=n+1;
		while(l<r){
			int mi=(l+r)/2;
			if(arr[mi]+brr[i]>sb[i])r=mi;
			else l=mi+1;
		}
		if(l==n+1){
			ans+=cb[i];
		}
		else if(l){
			ans+=cb[i];
			v[l].pb({i,-cb[i]});
		}
	}
	seg.init(m+1);
	for(int i=1;i<=n;i++){
		sort(v[i].begin(),v[i].end());
		for(int j=int(v[i].size())-1;j>0;j--){
			v[i][j-1].sc+=v[i][j].sc;
		}
		int las=0;
		for(auto x:v[i]){
			seg.rangeadd(las,x.fr-1,x.sc);
			las=x.fr;
		}
		las=0;
		for(auto x:v[i]){
			ll val=seg.query(las,x.fr-1);
			int loc=seg.walk(val);
			seg.rangeset(x.fr,loc-1,val);
		}
	}
	cout<<seg.query(0,m)+ans<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…