Submission #113583

#TimeUsernameProblemLanguageResultExecution timeMemory
113583MladenPPinball (JOI14_pinball)C++17
51 / 100
757 ms27384 KiB
#include<bits/stdc++.h> #define STIZE(x) fprintf(stderr, "STIZE%lld\n", x); #define PRINT(x) fprintf(stderr, "%s = %lld\n", #x, x); #define NL(x) printf("%c", " \n"[(x)]); #define lld long long #define pii pair<int,int> #define pb push_back #define fi first #define se second #define mid (l+r)/2 #define all(a) begin(a),end(a) #define sz(a) int((a).size()) #define LINF 1000000000000000000LL #define INF 1000000000 #define EPS 1e-9 using namespace std; #define MAXN 100010 lld a[MAXN], b[MAXN], c[MAXN], d[MAXN], segL[4*MAXN], segR[4*MAXN]; lld dpl[MAXN], dpr[MAXN]; set<int> hshs; map<int, int> hsh; void update(lld seg[], int node, int l, int r, int idx, lld val) { if(l == r) { seg[node] = min(seg[node], val); return; } if(idx <= mid) update(seg, 2*node, l, mid, idx, val); else update(seg, 2*node+1, mid+1, r, idx, val); seg[node] = min(seg[2*node], seg[2*node+1]); } lld query(lld seg[], int node, int l, int r, int L, int R) { if(L <= l && r <= R) return seg[node]; lld rez = LINF; if(L <= mid) rez = min(rez, query(seg, 2*node, l, mid, L, R)); if(R > mid) rez = min(rez, query(seg, 2*node+1, mid+1, r, L, R)); return rez; } int main() { ios::sync_with_stdio(false); cin.tie(0); fill(segL, segL+4*MAXN, LINF); fill(segR, segR+4*MAXN, LINF); int m, n; cin >> m >> n; hshs.insert(1); hshs.insert(n); for(int i = 1; i <= m; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; hshs.insert(a[i]); hshs.insert(b[i]); hshs.insert(c[i]); } int N = 0; for(auto x : hshs) hsh[x] = ++N; update(segL, 1, 1, N, 1, 0); update(segR, 1, 1, N, N, 0); lld rez = LINF; for(int i = 1; i <= m; i++) { a[i] = hsh[a[i]]; b[i] = hsh[b[i]]; c[i] = hsh[c[i]]; dpl[i] = query(segL, 1, 1, N, a[i], b[i]) + d[i]; dpr[i] = query(segR, 1, 1, N, a[i], b[i]) + d[i]; rez = min(rez, dpl[i]+dpr[i]-d[i]); update(segL, 1, 1, N, c[i], dpl[i]); update(segR, 1, 1, N, c[i], dpr[i]); } cout << (rez == LINF ? -1:rez); 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...