Submission #1185637

#TimeUsernameProblemLanguageResultExecution timeMemory
1185637nguynPinball (JOI14_pinball)C++20
100 / 100
216 ms46756 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define F first #define S second #define pb push_back #define pii pair<int,int> const int N = 3e5 + 5; int n, m, a[N], b[N], c[N], d[N]; pii fl[N], fr[N]; vector<int> cmp; pii stl[4 * N]; pii str[4 * N]; void update1(int id, int l, int r, int i, pii x) { if (l == r) { stl[id] = min(x, stl[id]); return; } int mid = (l + r) / 2; if (i > mid) { update1(id * 2 + 1, mid + 1, r, i, x); } else { update1(id * 2, l, mid, i, x); } stl[id] = min(stl[id * 2], stl[id * 2 + 1]); } void update2(int id, int l, int r, int i, pii x) { if (l == r) { str[id] = max(x, str[id]); return; } int mid = (l + r) / 2; if (i > mid) { update2(id * 2 + 1, mid + 1, r, i, x); } else { update2(id * 2, l, mid, i, x); } str[id] = max(str[id * 2], str[id * 2 + 1]); } pii get1(int id, int l, int r, int u, int v) { if (u <= l && r <= v) return stl[id]; int mid = (l + r) / 2; if (mid < u) return get1(id * 2 + 1, mid + 1, r, u, v); if (v <= mid) return get1(id * 2, l, mid, u, v); return min(get1(id * 2, l, mid, u, v), get1(id * 2 + 1, mid + 1, r, u, v)); } pii get2(int id, int l, int r, int u, int v) { if (u <= l && r <= v) return str[id]; int mid = (l + r) / 2; if (mid < u) return get2(id * 2 + 1, mid + 1, r, u, v); if (v <= mid) return get2(id * 2, l, mid, u, v); return max(get2(id * 2, l, mid, u, v), get2(id * 2 + 1, mid + 1, r, u, v)); } signed main(){ ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ; if (fopen("INP.INP" ,"r")) { freopen("INP.INP" ,"r" , stdin) ; freopen("OUT.OUT" , "w" , stdout) ; } cin >> m >> n; for (int i = 1; i <= m; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; cmp.pb(a[i]); cmp.pb(b[i]); cmp.pb(c[i]); } cmp.pb(1); cmp.pb(n); sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end()); n = cmp.size(); for (int i = 1; i <= m; i++) { a[i] = upper_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin(); b[i] = upper_bound(cmp.begin(), cmp.end(), b[i]) - cmp.begin(); c[i] = upper_bound(cmp.begin(), cmp.end(), c[i]) - cmp.begin(); } for (int i = 1; i <= 4 * n + 5; i++) { stl[i] = {1e18, 1e18}; str[i] = {-1e18, -1e18}; } int res = 1e18; for (int i = 1; i <= m; i++) { fl[i] = {a[i], d[i]}; fr[i] = {b[i], -d[i]}; // for (int j = 1; j < i; j++) { // if (a[i] <= c[j] && c[j] <= b[i]) { // pii x = fl[j]; // x.S += d[i]; // fl[i] = min(fl[i], x); // x = fr[j]; // x.S -= d[i]; // fr[i] = max(fr[i], x); // } // } pii x = get1(1, 1, n, a[i], b[i]); x.S += d[i]; fl[i] = min(fl[i], x); x = get2(1, 1, n, a[i], b[i]); x.S -= d[i]; fr[i] = max(fr[i], x); update1(1, 1, n, c[i], fl[i]); update2(1, 1, n, c[i], fr[i]); if (fl[i].F == 1 && fr[i].F == n) { res = min(res, fl[i].S - fr[i].S - d[i]); } } if (res == 1e18) cout << -1; else cout << res; }

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pinball.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...