Submission #755987

#TimeUsernameProblemLanguageResultExecution timeMemory
755987MohamedFaresNebiliPinball (JOI14_pinball)C++14
0 / 100
6 ms9812 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll int M, N, st[1200005]; array<int, 4> A[100005]; void update(int v, int l, int r, int p, int val) { if(l == r) { st[v] = min(st[v], val); return; } int md = (l + r) / 2; if(p <= md) update(v * 2, l, md, p, val); else update(v * 2 + 1, md + 1, r, p, val); st[v] = min(st[v * 2], st[v * 2 + 1]); } int query(int v, int l, int r, int lo, int hi) { if(l > hi || r < lo) return 1e18; if(l >= lo && r <= hi) return st[v]; return min(query(v * 2, l, (l + r) / 2, lo, hi), query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi)); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> M >> N; vector<int> comp; comp.push_back(N); for(int l = 0; l < M; l++) { cin >> A[l][0] >> A[l][1] >> A[l][2] >> A[l][3]; comp.push_back(A[l][0]); comp.push_back(A[l][1]); comp.push_back(A[l][2]); } sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); for(int l = 0; l < M; l++) { A[l][0] = lower_bound(comp.begin(), comp.end(), A[l][0]) - comp.begin(); A[l][1] = lower_bound(comp.begin(), comp.end(), A[l][1]) - comp.begin(); A[l][2] = lower_bound(comp.begin(), comp.end(), A[l][2]) - comp.begin(); } for(int l = 0; l < 1200005; l++) st[l] = 1e18; vector<int> L(M, 1e18); vector<int> R(M, 1e18); for(int l = 0; l < M; l++) { if(A[l][0] == 0) L[l] = A[l][3]; else L[l] = min(L[l], A[l][3] + query(1, 0, comp.size() - 1, A[l][0], A[l][1])); update(1, 0, comp.size() - 1, A[l][2], L[l]); } for(int l = 0; l < 1200005; l++) st[l] = 1e18; for(int l = 0; l < M; l++) { if(A[l][1] == comp.size() - 1) R[l] = A[l][3]; else R[l] = A[l][3] + query(1, 0, comp.size() - 1, A[l][0], A[l][1]); update(1, 0, comp.size() - 1, A[l][2], R[l]); } int res = 1e18; for(int l = 0; l < M; l++) res = min(res, L[l] + R[l] - A[l][3]); cout << (res == 1e18 ? -1 : res) << "\n"; }

Compilation message (stderr)

pinball.cpp: In function 'int32_t main()':
pinball.cpp:57:28: warning: comparison of integer expressions of different signedness: 'std::array<long long int, 4>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(A[l][1] == comp.size() - 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...