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
| #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int n, m, p; typedef pair<int, int> pii; pii ta[N], tb[N], a[N], b[N]; int ra[N], rb[N], sb[N]; bool cmp(const pii& a, const pii& b) { return a.first == b.first ? a.second > b.second:a.first < b.first; } struct X { int x, y, z; bool operator<(const X& b)const { return x < b.x; } }mon[N]; int S[N], top; #define mid ((l+r)>>1) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int tr[N << 2], laz[N << 2]; void build(int l, int r, int rt) { if (l == r) { tr[rt] = -sb[l]; return; } build(lson); build(rson); tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]); } void down(int rt) { int& x = laz[rt]; if (x) { tr[rt << 1] += x; tr[rt << 1 | 1] += x; laz[rt << 1] += x; laz[rt << 1 | 1] += x; x = 0; } } void add(int l, int r, int rt, int ql, int qr, int x) { if (ql <= l && qr >= r) { laz[rt] += x; tr[rt] += x; return; } down(rt); if (ql <= mid)add(lson, ql, qr, x); if (qr > mid)add(rson, ql, qr, x); tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]); } int query(int l, int r, int rt, int ql, int qr) { if (ql <= l && qr >= r)return tr[rt]; int ans = -INF; down(rt); if (ql <= mid)ans = max(ans, query(lson, ql, qr)); if (qr > mid)ans = max(ans, query(rson, ql, qr)); return ans; } int main() { scanf("%d%d%d", &n, &m, &p); for (int i = 1; i <= n; i++) scanf("%d%d", &ta[i].first, &ta[i].second); for (int i = 1; i <= m; i++) scanf("%d%d", &tb[i].first, &tb[i].second); for (int i = 1; i <= p; i++) scanf("%d%d%d", &mon[i].x, &mon[i].y, &mon[i].z); sort(ta + 1, ta + n + 1, cmp); sort(tb + 1, tb + m + 1, cmp); for (int i = 1; i <= n; i++) { while (top&&ta[S[top - 1]].second >= ta[i].second)top--; S[top++] = i; } n = top; while (top)a[top] = ta[S[top - 1]], top--; for (int i = 1; i <= n; i++)ra[i] = a[i].first; for (int i = 1; i <= m; i++) { while (top&&tb[S[top - 1]].second >= tb[i].second)top--; S[top++] = i; } m = top; while (top)b[top] = tb[S[top - 1]], top--; memset(sb, 0x3f, sizeof(sb)); for (int i = 1; i <= m; i++)rb[i] = b[i].first, sb[b[i].first] = b[i].second; for (int i = N - 2; i > 0; i--)sb[i] = min(sb[i], sb[i + 1]); build(1, N - 1, 1); int ans = -a[1].second - b[1].second; sort(mon + 1, mon + p + 1); for (int i = 1; i <= p; i++) { add(1, N - 1, 1, mon[i].y + 1, N - 1, mon[i].z); int p1 = upper_bound(ra + 1, ra + n + 1, mon[i].x) - ra; int p2 = upper_bound(rb + 1, rb + m + 1, mon[i].y) - rb; if (p1 == n + 1 || p2 == m + 1)continue; ans = max(ans, -a[p1].second + query(1, N - 1, 1, rb[p2], N - 1)); } printf("%d\n", ans); return 0; }
|