Submission #212060

#	Time	Username	Problem	Language	Result	Execution time	Memory
212060		NONAME	Pod starim krovovima (COCI20_psk)	C++17	0 / 50	243 ms	524288 KiB

Main

//#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;
}

• Subtask 1: 0 / 50