Submission #955012

#TimeUsernameProblemLanguageResultExecution timeMemory
955012underwaterkillerwhalePinball (JOI14_pinball)C++17
0 / 100
1 ms6492 KiB
#include <bits/stdc++.h> #define se second #define fs first #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 1e6 + 7; const int Mod = 1e9 + 7; const int szBL = 500; const ll INF = 1e18; const int BASE = 137; int n, m, num_values; struct Interval { int A, B, C, D; }a[N]; vector<int> Nen; ll prefix[N], suffix[N]; struct Segment_Tree { int Range; ll st[N << 2]; void init (int n) { Range = n; rep (i, 1, n << 2) st[i] = INF; } void update (int id, int l, int r, int pos, ll val) { if (l > pos || r < pos) return; if (l == r) { st[id] = min(st[id], val); return; } int mid = l + r >> 1; update (id << 1, l, mid, pos, val); update (id << 1 | 1, mid + 1, r, pos, val); st[id]= min(st[id << 1], st[id << 1 | 1]); } ll get (int id, int l, int r, int u, int v) { if (l > v || r < u) return INF; if (l >= u && r <= v) return st[id]; int mid = l + r >> 1; return min (get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v)); } void update (int pos, ll val) { update (1, 1, Range, pos, val); } ll get (int u, int v) { return get (1, 1, Range, u, v); } }ST; int CPR (int X) { return lower_bound(ALL(Nen), X) - Nen.begin() + 1; } void compress () { Nen = {1, m}; rep (i, 1, n) Nen.push_back(a[i].A), Nen.push_back(a[i].B), Nen.pb(a[i].C); sort (ALL(Nen)); Nen.resize(unique(ALL(Nen)) - Nen.begin()); num_values = SZ(Nen); rep (i, 1, n) { a[i].A = CPR(a[i].A), a[i].B = CPR(a[i].B), a[i].C = CPR(a[i].C); } } void solution() { cin >> n >> m; rep (i, 1, n) { cin >> a[i].A >> a[i].B >> a[i].C >> a[i].D; } compress(); // num_values = 10; // rep (i, 1, n) { // cout << a[i].A << " "<<a[i].B << " "<<a[i].C<<" "<<a[i].D<<"\n"; // } ST.init(num_values); rep (i, 1, n) { prefix[i] = ST.get(a[i].A, a[i].B) + a[i].D; if (a[i].A == 1) prefix[i] = a[i].D; ST.update(a[i].C, prefix[i]); // cout << i << " "<<prefix[i] <<"\n"; } ST.init(num_values); rep (i, 1, n) { suffix[i] = ST.get(a[i].A, a[i].B) + a[i].D; if (a[i].B == m) suffix[i] = a[i].D; ST.update (a[i].C, suffix[i]); } ll res = INF; rep (i, 1, n) { res = min(res, prefix[i] + suffix[i] - a[i].D); } if (res >= INF) cout << -1 <<"\n"; else cout << res <<"\n"; } #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); int main() { // file("c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll num_Test = 1; // cin >> num_Test; while(num_Test--) solution(); } /* */

Compilation message (stderr)

pinball.cpp: In member function 'void Segment_Tree::update(int, int, int, int, long long int)':
pinball.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = l + r >> 1;
      |                   ~~^~~
pinball.cpp: In member function 'long long int Segment_Tree::get(int, int, int, int, int)':
pinball.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 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...