-
Notifications
You must be signed in to change notification settings - Fork 0
/
pizza_cutter.cpp
57 lines (49 loc) · 1.28 KB
/
pizza_cutter.cpp
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
// iagorrr ;)
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using ll = long long;
#define all(x) x.begin(), x.end()
using pll = pair<ll,ll>;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void solve(){
ll n, m;
cin >> n >> m;
ll h, v;
cin >> h >> v;
vector<pair<ll, ll>> hori(h), vert(v);
for (auto &[x, y] : hori) cin >> x >> y;
for (auto &[x, y] : vert) cin >> x >> y;
sort(all(hori), [](pair<ll, ll> a, pair<ll, ll> b){
return a.second > b.second;
});
sort(all(vert), [](pair<ll, ll> a, pair<ll, ll> b){
return a.second > b.second;
});
ordered_set<ll> hori_x, vert_x;
ll total_hori = 0;
for (ll i = 0; i < h; i++)
{
auto total = hori_x.order_of_key(hori[i].first);
total_hori += total;
hori_x.insert(hori[i].first);
}
ll total_vert = 0;
for (ll i = 0; i < v; i++)
{
auto total = vert_x.order_of_key(vert[i].first);
total_vert += total;
vert_x.insert(vert[i].first);
}
auto ans = (h+1)*(v+1) + total_hori + total_vert;
cout << ans << '\n';
}
int32_t main() {
fastio;
solve();
}
// AC, ordered set, geometry.