| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 682550 |
2023-01-16T13:37:29 Z |
NK_ |
Pinball (JOI14_pinball) |
C++17 |
|
1 ms |
212 KB |
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = long long;
const ll INFL = ll(1e18) + 10;
struct Seg {
const ll ID = INFL; ll comb(ll a, ll b) { return min(a, b); }
vector<ll> seg; int n;
void init(int _n) {
n = _n;
seg.assign(2*n, ID);
}
void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }
void set(int p, ll x) {
p += n; seg[p] = min(seg[p], x); for(p /= 2; p; p /= 2) pull(p);
}
ll query(int l, int r) {
ll ra, rb; ra = rb = ID;
for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra, seg[l++]);
if (r&1) rb = comb(seg[--r], rb);
}
return comb(ra, rb);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; cin >> N >> M;
vector<int> A(N), B(N), C(N);
vector<ll> L(N), R(N), D(N);
vector<int> X;
for(int i = 0; i < N; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
--A[i], --B[i], --C[i];
X.push_back(A[i]); X.push_back(B[i]); X.push_back(C[i]);
}
if (M == 1) {
cout << 0 << nl;
return 0;
}
sort(begin(X), end(X)); X.erase(unique(begin(X), end(X)), end(X));
for(auto &x : A) x = lower_bound(begin(X), end(X), x) - begin(X);
for(auto &x : B) x = lower_bound(begin(X), end(X), x) - begin(X);
for(auto &x : C) x = lower_bound(begin(X), end(X), x) - begin(X);
int K = size(X);
for(int t = 0; t < 2; t++) {
Seg st; st.init(K);
st.set(0, 0);
for(int i = 0; i < N; i++) {
L[i] = st.query(A[i], B[i]) + D[i];
st.set(C[i], L[i]);
A[i] = K-1-A[i];
B[i] = K-1-B[i];
C[i] = K-1-C[i];
swap(A[i], B[i]);
}
L.swap(R);
}
ll ans = INFL;
for(int i = 0; i < N; i++) ans = min(ans, L[i] + R[i] - D[i]);
cout << (ans == INFL ? -1 : ans) << nl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
