Submission #66090

#TimeUsernameProblemLanguageResultExecution timeMemory
66090SpeedOfMagicPinball (JOI14_pinball)C++17
100 / 100
500 ms15984 KiB
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/ #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") template<typename T> using v = vector<T>; #define int long long typedef long double ld; typedef string str; typedef vector<int> vint; #define rep(a, l, r) for(int a = (l); a < (r); a++) #define pb push_back #define sz(a) ((int) a.size()) const long long inf = 4611686018427387903; //2^62 - 1 #if 0 //FileIO const string fileName = ""; ifstream fin ((fileName == "" ? "input.txt" : fileName + ".in" )); ofstream fout((fileName == "" ? "output.txt" : fileName + ".out")); #define get fin>> #define put fout<< #else #define get cin>> #define put cout<< #endif #define eol put endl #define check(a) put #a << ": " << a << endl; void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg) ;read(args...) ;} void print(){} template<typename Arg,typename... Args> void print(Arg arg,Args... args){put (arg)<<" ";print(args...);} void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg arg,Args... args){put (arg)<<" ";debug(args...);} int getInt(){int a; get a; return a;} //code goes here vint segTree; int tot; void init(int n) { tot = n; while (tot & (tot - 1)) tot++; segTree = vint(2 * tot); rep(i, 1, tot * 2) segTree[i] = inf; } int query(int l, int r, int cur = 1, int ll = 1, int rr = tot) { if (l > r) return inf; if (l == ll && r == rr) return segTree[cur]; int p = (ll + rr) / 2; return min(query(l, min(r, p), cur * 2, ll, p), query(max(l, p + 1), r, cur * 2 + 1, p + 1, rr)); } void update(int pos, int val, int cur = 1, int ll = 1, int rr = tot) { if (ll == rr) { segTree[cur] = min(segTree[cur], val); return; } int p = (ll + rr) / 2; if (pos <= p) update(pos, val, cur * 2, ll, p); else update(pos, val, cur * 2 + 1, p + 1, rr); segTree[cur] = min(segTree[cur * 2], segTree[cur * 2 + 1]); } void run() { int m, n; read(m, n); int a[m], b[m], c[m], d[m]; vint all; bool first[m], last[m]; rep(i, 0, m) { read(a[i], b[i], c[i], d[i]); first[i] = (a[i] == 1); last[i] = (b[i] == n); all.pb(c[i]); } sort(all.begin(), all.end()); map<int, int> hsh; int p = 1; rep(i, 0, sz(all)) if ((i && all[i] != all[i - 1]) || (!i)) hsh[all[i]] = p++; n = -inf; rep(i, 0, m) { a[i] = (*hsh.lower_bound(a[i])).second; auto dd = hsh.upper_bound(b[i]); dd--; b[i] = (*dd).second; c[i] = hsh[c[i]]; n = max(n, b[i]); } int dp[2][m]; rep(k, 0, 2) { init(n); rep(i, 0, m) { if ((!k && first[i]) || (k && last[i])) dp[k][i] = d[i]; else dp[k][i] = min(inf, query(a[i], b[i]) + d[i]); update(c[i], dp[k][i]); } } //rep(i, 0, 2) { rep(j, 0, m) print(dp[i][j]); eol; } int ans = inf; rep(i, 0, m) ans = min(ans, dp[0][i] + dp[1][i] - d[i]); if (ans == inf) put -1; else put ans; } int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); 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...