aboutsummaryrefslogtreecommitdiff
path: root/20/jan/gold/boards.cpp
diff options
context:
space:
mode:
Diffstat (limited to '20/jan/gold/boards.cpp')
-rw-r--r--20/jan/gold/boards.cpp50
1 files changed, 50 insertions, 0 deletions
diff --git a/20/jan/gold/boards.cpp b/20/jan/gold/boards.cpp
new file mode 100644
index 0000000..812c959
--- /dev/null
+++ b/20/jan/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);
+}