| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 854143 |
2023-09-26T08:32:03 Z |
Desh03 |
Pinball (JOI14_pinball) |
C++17 |
|
195 ms |
524288 KB |
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
template<typename T>
struct SegmentTree {
vector<T> st;
int n;
SegmentTree(int n_) : n(n_) {
st.resize(n << 1, INF);
}
void update(int i, T x) {
i += n;
st[i] = min(st[i], x);
while (i >>= 1) st[i] = min(st[i << 1], st[i << 1 | 1]);
}
T query(int l, int r) {
T mn = INF;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) mn = min(mn, st[l++]);
if (r & 1) mn = min(mn, st[--r]);
}
return mn;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int m, n;
cin >> m >> n;
SegmentTree<long long> l(n), r(n);
long long ans = INF;
while (m--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
--a, --c;
if (!a && b == n) {
ans = min(ans, (long long) d);
} else if (!a) {
long long y = r.query(a, b);
if (y != INF) {
ans = min(ans, d + y);
r.update(c, d + y);
}
l.update(c, d);
} else if (b == n) {
long long x = l.query(a, b);
if (x != INF) {
ans = min(ans, x + d);
l.update(c, x + d);
}
r.update(c, d);
} else {
long long x = l.query(a, b), y = r.query(a, b);
ans = min(ans, x + y + d);
if (x != INF) {
l.update(c, x + d);
}
if (y != INF) {
r.update(c, y + d);
}
}
}
cout << (ans == INF ? -1 : ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
548 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
548 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
7 ms |
31556 KB |
Output is correct |
| 10 |
Correct |
65 ms |
313316 KB |
Output is correct |
| 11 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
548 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
7 ms |
31556 KB |
Output is correct |
| 10 |
Correct |
65 ms |
313316 KB |
Output is correct |
| 11 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
548 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
7 ms |
31556 KB |
Output is correct |
| 10 |
Correct |
65 ms |
313316 KB |
Output is correct |
| 11 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
