제출 #1370487

#제출 시각아이디문제언어결과실행 시간메모리
1370487PieArmyTwo Dishes (JOI19_dishes)C++20
5 / 100
176 ms52172 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)

struct Seg{
	int n;
	vector<ll>tree;
	vector<int>lazy;
	vector<pair<ll,int>>suf;
	void init(int N){
		n=N;
		tree.resize(n<<2,0);
		lazy.resize(n<<2,0);
		suf.resize(n<<2,{0,1});
	}
	void push(int node,int left,int right){
		if(lazy[node]==0)return;
		tree[node]=0;
		suf[node]={0,1};
		if(left!=right){
			lazy[node*2]=lazy[node*2+1]=lazy[node];
		}
		lazy[node]=0;
	}
	int l,r;
	void up(int node=1,int left=1,int right=-1){
		if(right==-1)right=n;
		push(node,left,right);
		if(left==right){
			tree[node]+=r;
			suf[node]={tree[node],1};
			return;
		}
		if(l>mid){
			push(node*2,left,mid);
			up(node*2+1,mid+1,right);
		}
		else{
			push(node*2+1,mid+1,right);
			up(node*2,left,mid);
		}
		tree[node]=tree[node*2]+tree[node*2+1];
		suf[node]=max(suf[node*2+1],{suf[node*2].fr+tree[node*2+1],right-mid+suf[node*2].sc});
	}
	void update(int tar,int x){
		l=tar;r=x;
		up();
	}
	void sil(int node=1,int left=1,int right=-1){
		if(right==-1)right=n;
		if(left>=l&&right<=r){
			lazy[node]=1;
			push(node,left,right);
			return;
		}
		push(node,left,right);
		if(left>r||right<l)return;
		sil(node*2,left,mid);
		sil(node*2+1,mid+1,right);
		tree[node]=tree[node*2]+tree[node*2+1];
		suf[node]=max(suf[node*2+1],{suf[node*2].fr+tree[node*2+1],right-mid+suf[node*2].sc});
	}
	void yoket(int left,int right){
		l=left;r=right;
		sil();
	}
	ll qu(int node=1,int left=1,int right=-1){
		if(right==-1)right=n;
		if(left>r||right<l)return 0;
		push(node,left,right);
		if(left>=l&&right<=r)return tree[node];
		return qu(node*2,left,mid)+qu(node*2+1,mid+1,right);
	}
	ll query(int left,int right){
		l=left;r=right;
		return qu();
	}
	ll get(){
		push(0,1,n);
		if(suf[1].fr<=0)return 0;
		ll res=suf[1].fr;
		yoket(n-suf[1].sc+1,n);
		return res;
	}
};

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

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){
			if(ca[i]>0){
				a[i].pb({l,ca[i]});
			}
			else{
				b[i].pb({l,-ca[i]});
			}
		}
	}
	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];
			if(cb[i]>0){
				b[l].pb({i,cb[i]});
			}
			else{
				a[l].pb({i,-cb[i]});
			}
		}
	}
	seg.init(m);
	for(int i=1;i<=n;i++){
		for(auto x:b[i]){
			seg.update(x.fr,-x.sc);
		}
		for(auto x:a[i]){
			seg.update(x.fr,x.sc);
			ans+=seg.get();
		}
	}
	cout<<ans<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…