1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 200005;
int n, m, p, wid, aid;
LL ans = -1e16, fun[1123456];
struct Weapon{
LL att, cost;
bool operator < (const Weapon &A) const{
return att == A.att ? cost < A.cost : att < A.att;
}
}w[N];
struct Armor{
LL def, cost;
bool operator < (const Armor &A) const{
return def == A.def ? cost < A.cost : def < A.def;
}
}a[N];
struct Monster{
LL att, def, cost;
bool operator < (const Monster &A) const{
return def < A.def;
}
}mon[N];
struct segTree{
int l, r;
LL mxc, lazy;
}tr[4123456];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
tr[id].mxc = max(tr[lid].mxc, tr[rid].mxc);
}
inline void pushdown(int id){
if(tr[id].l == tr[id].r) return;
if(tr[id].lazy){
tr[lid].lazy += tr[id].lazy;
tr[lid].mxc += tr[id].lazy;
tr[rid].lazy += tr[id].lazy;
tr[rid].mxc += tr[id].lazy;
tr[id].lazy = 0;
}
}
void build(int id, int l, int r){
tr[id].l = l, tr[id].r = r;
if(tr[id].l == tr[id].r){
if(fun[tr[id].l]) tr[id].mxc = -fun[tr[id].l];
else tr[id].mxc = -1e16;
return;
}
build(lid, l, mid);
build(rid, mid+1, r);
pushup(id);
}
void add(int id, int l, int r, int val){
pushdown(id);
if(tr[id].l == l && tr[id].r == r){
tr[id].lazy += val;
tr[id].mxc += val;
return;
}
if(r <= mid) add(lid, l, r, val);
else if(l > mid) add(rid, l, r, val);
else add(lid, l, mid, val), add(rid, mid+1, r, val);
pushup(id);
}
int query(int id, int l, int r){
pushdown(id);
if(tr[id].l == l && tr[id].r == r) return tr[id].mxc;
if(r <= mid) return query(lid, l, r);
else if(l > mid) return query(rid, l, r);
else return max(query(lid, l, mid), query(rid, mid+1, r));
}
int main(){
read(n, m, p);
for(int i = 1; i <= n; i++) read(w[i].att, w[i].cost);
for(int i = 1; i <= m; i++) read(a[i].def, a[i].cost);
for(int i = 1; i <= p; i++) read(mon[i].def, mon[i].att, mon[i].cost);
sort(w+1, w+n+1);
sort(a+1, a+m+1);
sort(mon+1, mon+p+1);
for(int i = 1; i <= n; i++) if(w[i].att != w[i-1].att) w[++wid] = w[i];
for(int i = 1; i <= m; i++) if(a[i].def != a[i-1].def) a[++aid] = a[i];
for(int i = 1; i <= aid; i++) fun[a[i].def] = a[i].cost;
build(1, 1, 1e6+5);
int pt = 0;
for(int i = 1; i <= wid; i++){
while(pt < p && mon[pt+1].def < w[i].att){
pt++;
add(1, mon[pt].att+1, 1e6+5, mon[pt].cost);
}
ans = max(ans, query(1, 1, 1e6+5) - w[i].cost);
}
printf("%lld\n", ans);
return 0;
}
|