Submission #269377

#TimeUsernameProblemLanguageResultExecution timeMemory
269377imeimi2000Pinball (JOI14_pinball)C++17
100 / 100
360 ms10420 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; const llong inf = 1e16; int sz; struct seg { llong dat[1 << 18]; seg() { for (int i = 0; i < (1 << 18); ++i) { dat[i] = inf; } } void update(int i, int s, int e, int x, llong v) { if (s == e) { dat[i] = min(dat[i], v); return; } int m = (s + e) / 2; if (x <= m) update(i << 1, s, m, x, v); else update(i << 1 | 1, m + 1, e, x, v); dat[i] = min(dat[i << 1], dat[i << 1 | 1]); } void update(int x, llong v) { update(1, 0, sz, x, v); } llong query(int i, int s, int e, int x, int y) const { if (e < x || y < s) return inf; if (x <= s && e <= y) return dat[i]; int m = (s + e) / 2; return min(query(i << 1, s, m, x, y) , query(i << 1 | 1, m + 1, e, x, y)); } llong query(int x, int y) const { return query(1, 0, sz, x, y); } } lseg, rseg; int m, n; int a[100001], b[100001], c[100001], d[100001]; vector<int> comp; int find(int x) { return lower_bound(comp.begin(), comp.end(), x) - comp.begin(); } int main() { scanf("%d%d", &m, &n); for (int i = 0; i < m; ++i) { scanf("%d%d%d%d", a + i, b + i, c + i, d + i); comp.push_back(c[i]); } comp.push_back(1); comp.push_back(n); sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); sz = comp.size() - 1; for (int i = 0; i < m; ++i) { a[i] = find(a[i]); b[i] = find(b[i] + 1) - 1; c[i] = find(c[i]); } lseg.update(0, 0); rseg.update(sz, 0); llong ans = inf; for (int i = 0; i < m; ++i) { ans = min(ans, lseg.query(a[i], b[i]) + rseg.query(a[i], b[i]) + d[i]); lseg.update(c[i], lseg.query(a[i], c[i]) + d[i]); rseg.update(c[i], rseg.query(c[i], b[i]) + d[i]); } printf("%lld\n", ans < inf ? ans : -1); return 0; }

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |     scanf("%d%d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         scanf("%d%d%d%d", a + i, b + i, c + i, d + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...