| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 301659 |
2020-09-18T05:46:06 Z |
E869120 |
Pinball (JOI14_pinball) |
C++14 |
|
731 ms |
31192 KB |
#include <bits/stdc++.h>
using namespace std;
class RangeMin {
public:
int size_ = 1;
vector<long long> dat;
void init(int sz) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, 0);
}
void update(int pos, long long x) {
pos += size_;
dat[pos] = x;
while (pos >= 2) {
pos >>= 1;
dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (r <= a || b <= l) return (1LL << 60);
long long v1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return min(v1, v2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
long long N, L;
long long A[1 << 19], B[1 << 19], C[1 << 19], D[1 << 19];
long long dpl[1 << 19];
long long dpr[1 << 19];
RangeMin ZL, ZR;
vector<long long> X;
int main() {
// INPUT
cin >> N >> L;
for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];
// ZAATS
for (int i = 0; i < N; i++) X.push_back(A[i]);
for (int i = 0; i < N; i++) X.push_back(B[i] + 1);
for (int i = 0; i < N; i++) X.push_back(C[i]);
X.push_back(1);
X.push_back(L + 1);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
for (int i = 0; i < N; i++) A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
for (int i = 0; i < N; i++) B[i] = lower_bound(X.begin(), X.end(), B[i] + 1) - X.begin();
for (int i = 0; i < N; i++) C[i] = lower_bound(X.begin(), X.end(), C[i]) - X.begin();
// PRCLC
long long Answer = (1LL << 60);
ZL.init(X.size() + 2);
ZR.init(X.size() + 2);
for (int i = 0; i < (int)X.size(); i++) dpl[i] = (1LL << 60);
for (int i = 0; i < (int)X.size(); i++) dpr[i] = (1LL << 60);
dpl[0] = 0;
dpr[X.size() - 2] = 0;
for (int i = 0; i < (int)X.size(); i++) ZL.update(i, dpl[i]);
for (int i = 0; i < (int)X.size(); i++) ZR.update(i, dpr[i]);
// CALCS
for (int i = 0; i < N; i++) {
long long val1 = ZL.query(A[i], B[i]);
long long val2 = ZR.query(A[i], B[i]);
Answer = min(Answer, val1 + val2 + D[i]);
dpl[C[i]] = min(dpl[C[i]], val1 + D[i]);
dpr[C[i]] = min(dpr[C[i]], val2 + D[i]);
ZL.update(C[i], dpl[C[i]]);
ZR.update(C[i], dpr[C[i]]);
//cout << val1 << " " << val2 << endl;
}
// FINAL
if (Answer == (1LL << 60)) cout << "-1" << endl;
else cout << Answer << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
7 ms |
544 KB |
Output is correct |
| 18 |
Correct |
4 ms |
512 KB |
Output is correct |
| 19 |
Correct |
6 ms |
616 KB |
Output is correct |
| 20 |
Correct |
5 ms |
512 KB |
Output is correct |
| 21 |
Correct |
3 ms |
512 KB |
Output is correct |
| 22 |
Correct |
5 ms |
640 KB |
Output is correct |
| 23 |
Correct |
5 ms |
640 KB |
Output is correct |
| 24 |
Correct |
5 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
7 ms |
544 KB |
Output is correct |
| 18 |
Correct |
4 ms |
512 KB |
Output is correct |
| 19 |
Correct |
6 ms |
616 KB |
Output is correct |
| 20 |
Correct |
5 ms |
512 KB |
Output is correct |
| 21 |
Correct |
3 ms |
512 KB |
Output is correct |
| 22 |
Correct |
5 ms |
640 KB |
Output is correct |
| 23 |
Correct |
5 ms |
640 KB |
Output is correct |
| 24 |
Correct |
5 ms |
640 KB |
Output is correct |
| 25 |
Correct |
41 ms |
2036 KB |
Output is correct |
| 26 |
Correct |
124 ms |
5612 KB |
Output is correct |
| 27 |
Correct |
380 ms |
12328 KB |
Output is correct |
| 28 |
Correct |
418 ms |
11496 KB |
Output is correct |
| 29 |
Correct |
298 ms |
10596 KB |
Output is correct |
| 30 |
Correct |
474 ms |
11624 KB |
Output is correct |
| 31 |
Correct |
633 ms |
15908 KB |
Output is correct |
| 32 |
Correct |
559 ms |
15068 KB |
Output is correct |
| 33 |
Correct |
96 ms |
5288 KB |
Output is correct |
| 34 |
Correct |
346 ms |
15716 KB |
Output is correct |
| 35 |
Correct |
512 ms |
30944 KB |
Output is correct |
| 36 |
Correct |
731 ms |
31192 KB |
Output is correct |
| 37 |
Correct |
631 ms |
30980 KB |
Output is correct |
| 38 |
Correct |
599 ms |
31100 KB |
Output is correct |
