[Link] https://www.acmicpc.net/problem/7626
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
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
struct line {
int x;
int uy, ly;
bool start;
};
int n;
vector<int> seg;
vector<int> cnt;
vector<line> lines;
vector<int> y_values;
ll tot_size;
void update(int idx, int cl, int cr, int tl, int tr, int dval) {
if(cr < tl || tr < cl) return;
if(tl <= cl && cr <= tr) cnt[idx] += dval;
else {
ll mid = (cl + cr) / 2;
update(idx<<1, cl, mid, tl, tr, dval);
update(idx<<1|1, mid + 1, cr, tl, tr, dval);
}
if(cnt[idx]) seg[idx] = y_values[cr + 1] - y_values[cl];
else {
if(cl == cr) seg[idx] = 0;
else seg[idx] = seg[idx<<1] + seg[idx<<1|1];
}
}
int main() {
FASTIO; cin >> n;
for0(i, n) {
line sline, eline; sline.start = 1, eline.start = 0;
cin >> sline.x >> eline.x >> sline.ly >> sline.uy;
eline.ly = sline.ly, eline.uy = sline.uy;
lines.push_back(sline); lines.push_back(eline);
y_values.push_back(sline.ly); y_values.push_back(sline.uy);
}
sort(y_values.begin(), y_values.end());
y_values.erase(unique(y_values.begin(), y_values.end()), y_values.end());
int N = 1 << (int)(ceil(log2(y_values.size()) + 1));
seg.resize(N); cnt.resize(N);
sort(lines.begin(), lines.end(), [](line l1, line l2) { return l1.x < l2.x; });
vector<int>::iterator start_iter = y_values.begin();
for0(i, lines.size() - 1) {
int rank_1 = lower_bound(start_iter, y_values.end(), lines[i].ly) - start_iter;
int rank_2 = lower_bound(start_iter, y_values.end(), lines[i].uy) - start_iter;
update(1, 0, y_values.size() - 1, rank_1, rank_2 - 1, lines[i].start ? 1 : -1);
tot_size += (ll)seg[1] * (lines[i+1].x - lines[i].x);
}
cout << tot_size;
return 0;
}