//#NDEBUG
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
using namespace std;
//using namespace __gnu_pbds;
#define pb push_back
#define S second
#define F first
#define N 200015
#define M ll(1e9 + 7)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair <ll, ll> pt;
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
bool cmp(pair <pair <ll, ll>, ll> x, pair <pair <ll, ll>, ll> y) {return x.F.F < y.F.F;}
bool cmpr(pair <pair <ll, ll>, ll> x, pair <pair <ll, ll>, ll> y) {return x.F.S < y.F.S;}
ll t[N * 4], psh[N * 4];
void build(int v, int tl, int tr)
{
psh[v] = 0;
t[v] = 0;
if (tl != tr)
{
int md = (tl + tr) >> 1;
build(v + v, tl, md);
build(v + v + 1, md + 1, tr);
}
}
void Push(int v, int tl, int tr)
{
if (psh[v] == 0) return;
if (tl == tr) t[v] += psh[v];
else
{
psh[v + v] += psh[v];
psh[v + v + 1] += psh[v];
}
psh[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, ll val)
{
Push(v, tl, tr);
if (tl > tr || tr < l || r < tl) return;
if (l <= tl && tr <= r) {psh[v] += val; Push(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd(v + v, tl, md, l, r, val);
upd(v + v + 1, md + 1, tr, l, r, val);
}
ll gt(int v, int tl, int tr, int pos)
{
Push(v, tl, tr);
if (tl == tr) return t[v];
int md = (tl + tr) >> 1;
if (pos <= md) return gt(v + v, tl, md, pos);
return gt(v + v + 1, md + 1, tr, pos);
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, m, p;
cin >> n >> m >> p;
vector <pair <ll, ll> > g, v; g.resize(n); v.resize(m);
for (ll i = 0; i < n; i++) cin >> g[i].F >> g[i].S;
for (ll i = 0; i < m; i++) cin >> v[i].F >> v[i].S;
vector <pair <pair <ll, ll>, ll> > gr; gr.resize(p);
for (ll i = 0; i < p; i++) cin >> gr[i].F.F >> gr[i].F.S >> gr[i].S;
sort(gr.begin(), gr.end(), cmp);
sort(g.begin(), g.end());
sort(v.begin(), v.end());
vector <ll> dix; dix.resize(n);
for (int i = 0; i < n; i++) dix[i] = g[i].F;
ll as = -1e18, j = 0;
build(1, 0, n - 1);
for (int i = 0; i < p; i++)
{
while (j < m && v[j].F <= gr[i].F.S) j++;
int it = upper_bound(dix.begin(), dix.end(), gr[i].F.F) - dix.begin() - 1;
it++;
if (it != n)
{
upd(1, 0, n - 1, it, n - 1, gr[i].S);
ll sum = gt(1, 0, n - 1, it);
if (j != m) as = max(as, sum - v[j].S - g[it].S);
}
}
sort(gr.begin(), gr.end(), cmpr);
dix.resize(m);
for (int i = 0; i < m; i++) dix[i] = v[i].F;
j = 0;
build(1, 0, m - 1);
for (int i = 0; i < p; i++)
{
while (j < n && g[j].F <= gr[i].F.F) j++;
int it = upper_bound(dix.begin(), dix.end(), gr[i].F.S) - dix.begin() - 1;
it++;
if (it != m)
{
upd(1, 0, m - 1, it, m - 1, gr[i].S);
ll sum = gt(1, 0, m - 1, it);
if (j != n) as = max(as, sum - v[it].S - g[j].S);
}
}
cout << as;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 2 |
Incorrect |
4 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 3 |
Incorrect |
5 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 4 |
Incorrect |
4 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 5 |
Incorrect |
5 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 6 |
Incorrect |
5 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 7 |
Incorrect |
5 ms |
384 KB |
Expected int32, but "-1000000000000000000" found |
| 8 |
Incorrect |
18 ms |
2688 KB |
Expected int32, but "-1000000000000000000" found |
| 9 |
Runtime error |
243 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
237 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
