diff options
| -rw-r--r-- | 2020/January/Gold/boards.cpp | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/2020/January/Gold/boards.cpp b/2020/January/Gold/boards.cpp new file mode 100644 index 0000000..812c959 --- /dev/null +++ b/2020/January/Gold/boards.cpp @@ -0,0 +1,50 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +typedef pair<int, int> ii; +constexpr int INF = 1e9; + +struct node { + int val; node* c[2]; + node() { val = -INF; c[0] = c[1] = 0; } + node* get_c(int i) { return (!c[i] ? c[i] = new node : c[i]); } + void update(int x, int v, int l = 0, int r = INF) { + if (l == r) val = max(v, val); + else { + int m = (l + r) >> 1; + x <= m ? get_c(0)->update(x, v, l, m) : get_c(1)->update(x, v, m + 1, r); + val = max(c[0] ? c[0]->val : -INF, c[1] ? c[1]->val : -INF); + } + } + int query(int a, int b, int l = 0, int r = INF) { + if (a > r || b < l) return -INF; + if (a <= l && b >= r) return val; + int m = (l + r) >> 1; + return max(c[0] ? c[0]->query(a, b, l, m) : -INF, c[1] ? c[1]->query(a, b, m + 1, r) : -INF); + } +} seg; + +pair<ii, ii> A[100001]; + +int main() { + ifstream cin("boards.in"); + ofstream cout("boards.out"); + + int N, P; + cin >> N >> P; + for (int i = 0; i < P; ++i) cin >> A[i].f.f >> A[i].f.s >> A[i].s.f >> A[i].s.s; + sort(A, A + P); + + seg.update(0, 0); + set<pair<ii, int>> S; + for (int i = 0; i < P; ++i) { + S.emplace(A[i].s, A[i].f.f + A[i].f.s - seg.query(0, A[i].f.s)); + auto it = S.begin(); + while (it != S.end() && it->f.f <= (i < P - 1 ? A[i + 1].f.f : INF)) { + seg.update(it->f.s, it->f.f + it->f.s - it->s); + it = S.erase(it); + } + } + cout << 2 * N - seg.query(0, N); +} |