제출 #18074

#제출 시각아이디문제언어결과실행 시간메모리
18074tncks0121Pinball (JOI14_pinball)C++14
100 / 100
437 ms33160 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <deque> #include <utility> #include <bitset> #include <limits.h> #include <time.h> #include <functional> #include <numeric> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; const int M_ = 100500; const ll oo = (ll)1e18; int M, N, X; struct device { int a, b, c, d; }; device devices[M_]; const int LEAF = 131072 * 4; const int TSZ = LEAF + LEAF + 2; struct minSegmentTree { ll tree[TSZ]; minSegmentTree() { fill(tree, tree + TSZ, oo); } void upd (int x, ll v) { x += LEAF; while(x > 0) { tree[x] = min(tree[x], v); x >>= 1; } } ll get (int x, int y) { ll ret = oo; x += LEAF; y += LEAF; while(x <= y) { if((x & 1) == 1) ret = min(ret, tree[x]); if((y & 1) == 0) ret = min(ret, tree[y]); x = (x + 1) >> 1; y = (y - 1) >> 1; } return ret; } }; minSegmentTree tree[2]; map<int, int> ren; int main() { scanf("%d%d", &M, &N); for(int i = 1; i <= M; i++) { device &d = devices[i]; scanf("%d%d%d%d", &d.a, &d.b, &d.c, &d.d); ren[d.a] = -1; ren[d.b] = -1; ren[d.c] = -1; } ren[1] = -1; ren[N] = -1; { int v = 0; for(auto &it : ren) it.second = ++v; for(int i = 1; i <= M; i++) { device &d = devices[i]; d.a = ren[d.a]; d.b = ren[d.b]; d.c = ren[d.c]; } X = ren[N]; } ll ans = oo; tree[0].upd(1, 0); tree[1].upd(X, 0); for(int i = 1; i <= M; i++) { device &d = devices[i]; ll v[2] = {oo, oo}; for(int t = 0; t < 2; t++) { v[t] = tree[t].get(d.a, d.b); if(v[t] < oo) { v[t] += d.d; tree[t].upd(d.c, v[t]); } } if(v[0] < oo && v[1] < oo) { ans = min(ans, v[0] + v[1] - d.d); } } if(ans >= oo) ans = -1; printf("%lld\n", ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...