1321E - World of Darkraft Battle for Azathoth - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n,m,p;
ll w[1<<20],ans=-LLONG_MAX;
struct evt{int x,y,c,tp;};basic_string<evt> ev;
struct segTree{
	struct node{ll mx,ad;}a[1<<21];
	void build(int p=1,int tl=1,int tr=1e6+1){
		if(tl==tr){a[p].mx=-w[tl];return;}
		int mid=tl+tr>>1;
		build(p*2,tl,mid),build(p*2+1,mid+1,tr);
		a[p].mx=max(a[p*2].mx,a[p*2+1].mx);
	}
	void ins(int x,int v,int p=1,int tl=1,int tr=1e6+1){
		if(x<=tl){a[p].ad+=v;a[p].mx+=v;return;}
		int mid=tl+tr>>1;
		if(x<=mid)ins(x,v,p*2,tl,mid);
		ins(x,v,p*2+1,mid+1,tr);
		a[p].mx=max(a[p*2].mx,a[p*2+1].mx)+a[p].ad;
	}
}tr;
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++){
		int a,ca;scanf("%d%d",&a,&ca);
		ev+={a,0,ca,0};
	}
	memset(w,0x3f,sizeof w);
	for(int i=1;i<=m;i++){
		int b,cb;scanf("%d%d",&b,&cb);
		w[b]=min(w[b],(ll)cb);
	}
	tr.build();
	for(int i=1;i<=p;i++){
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		ev+={x,y,c,1};
	}
	sort(ev.begin(),ev.end(),[](evt a,evt b){return a.x<b.x || a.x==b.x && a.tp<b.tp;});
	for(evt&x:ev)if(x.tp)
		tr.ins(x.y+1,x.c);
	else ans=max(ans,tr.a[1].mx-x.c);
	printf("%lld\n",ans);
	return 0;
}