Submission #36013

#TimeUsernameProblemLanguageResultExecution timeMemory
36013YoLoPinball (JOI14_pinball)C++14
0 / 100
9 ms14680 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define fi first #define se second #define int long long #define endl '\n' #define pi acos(-1) #define pque priority_queue #define N 1000000 #define lmax LONG_LONG_MAX typedef pair < int, int > ii; typedef vector < int > vi; typedef vector < vi > vii; int mod = 1000000007; int n, m, lef[100009], rig[100009], a[100009], b[100009], c[100009], d[100009], f[100009], itl[400009], itr[400009], p[100009], ans = lmax; void updl(int k, int l, int r, int pos, int val) { if(r < pos || l > pos || r < l) return; if(r == pos && l == pos) { itl[k] = val; return; } int mid = (l + r) / 2; updl(k * 2, l, mid, pos, val); updl(k * 2 + 1, mid + 1, r, pos, val); itl[k] = min(itl[k * 2], itl[k * 2 + 1]); } int getl(int k, int l, int r, int L, int R) { if(r < L || R < l || r < l) return 1e18; if(L <= l && r <= R) return itl[k]; int mid = (l + r) / 2; return min(getl(k * 2, l, mid, L, R), getl(k * 2 + 1, mid + 1, r, L, R)); } void updr(int k, int l, int r, int pos, int val) { if(r < pos || l > pos || r < l) return; if(r == pos && l == pos) { itr[k] = val; return; } int mid = (l + r) / 2; updr(k * 2, l, mid, pos, val); updr(k * 2 + 1, mid + 1, r, pos, val); itr[k] = min(itr[k * 2], itr[k * 2 + 1]); } int getr(int k, int l, int r, int L, int R) { if(r < L || R < l || r < l) return 1e18; if(L <= l && r <= R) return itr[k]; int mid = (l + r) / 2; return min(getr(k * 2, l, mid, L, R), getr(k * 2 + 1, mid + 1, r, L, R)); } bool cmp(int u, int v) { return c[u] < c[v]; } signed main() { ios_base::sync_with_stdio(0); cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i] >> c[i] >> d[i], f[i] = i; sort(f + 1, f + 1 + n, cmp); for(int i = 1; i <= n; i ++) p[f[i]] = i; for(int i = 1; i <= 400000; i ++) itl[i] = itr[i] = 1e18; for(int i = 1; i <= n; i ++) { int l = 1; int r = n; while(l < r) { int mid = (l + r) / 2; if(c[f[mid]] < a[i]) l = mid + 1; else r = mid; } int ll = l; l = 1; r = n; while(l < r) { int mid = (l + r + 1) / 2; if(c[f[mid]] > b[i]) r = mid - 1; else l = mid; } int rr = l; if(a[i] == 1) lef[i] = d[i]; else { int tak = getl(1, 1, n, ll, rr); if(tak < 1e18) lef[i] = tak + d[i]; } if(lef[i] > 0) updl(1, 1, n, p[i], lef[i]); if(b[i] == m) rig[i] = d[i]; else { int tak = getr(1, 1, n, ll, rr); if(tak < 1e18) rig[i] = tak + d[i]; } if(rig[i] > 0) updr(1, 1, n, p[i], rig[i]); if(rig[i] > 0 && lef[i] > 0) ans = min(ans, rig[i] + lef[i] - d[i]); cout << i << ' ' << l << ' ' << r << ' ' << p[i] << ' ' << lef[i] << ' ' << rig[i] << endl; } if(ans < 1e16) cout << ans; else cout << -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...