# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
40050 |
2018-01-26T01:50:56 Z |
funcsr |
Pinball (JOI14_pinball) |
C++14 |
|
511 ms |
23136 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define INF (1LL<<60)
#define MAX_N (1<<19)
struct SegTree {
long long seg[MAX_N*2-1];
SegTree() {
fill(seg, seg+MAX_N*2-1, INF);
}
void chmin(int k, long long v) {
k += MAX_N-1;
if (seg[k] <= v) return;
seg[k] = v;
while (k) {
k = (k-1) / 2;
seg[k] = min(seg[k*2+1], seg[k*2+2]);
}
}
long long query(int a, int b, int k=0, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return INF;
if (a <= l && r <= b) return seg[k];
return min(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
}
};
SegTree segL, segR;
int M, N;
int A[100000], B[100000], C[100000], D[100000];
int main() {
cin >> M >> N;
rep(i, M) cin >> A[i] >> B[i] >> C[i] >> D[i];
vector<int> xs;
rep(i, M) xs.pb(A[i]), xs.pb(B[i]), xs.pb(C[i]);
xs.pb(1);
xs.pb(N);
sort(all(xs)); uniq(xs);
rep(i, M) A[i] = index(xs, A[i]), B[i] = index(xs, B[i]), C[i] = index(xs, C[i]);
segR.chmin(xs.size()-1, 0);
segL.chmin(0, 0);
long long m = INF;
rep(i, M) {
m = min(m, segL.query(A[i], B[i]+1) + segR.query(A[i], B[i]+1) + D[i]);
segR.chmin(C[i], segR.query(A[i], B[i]+1) + D[i]);
segL.chmin(C[i], segL.query(A[i], B[i]+1) + D[i]);
}
if (m == INF) m = -1;
cout << m << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
19980 KB |
Output is correct |
2 |
Correct |
0 ms |
19980 KB |
Output is correct |
3 |
Correct |
0 ms |
19980 KB |
Output is correct |
4 |
Correct |
3 ms |
19980 KB |
Output is correct |
5 |
Correct |
7 ms |
19980 KB |
Output is correct |
6 |
Correct |
3 ms |
19980 KB |
Output is correct |
7 |
Correct |
5 ms |
19980 KB |
Output is correct |
8 |
Correct |
0 ms |
19980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
19980 KB |
Output is correct |
2 |
Correct |
3 ms |
19980 KB |
Output is correct |
3 |
Correct |
8 ms |
19980 KB |
Output is correct |
4 |
Correct |
3 ms |
19980 KB |
Output is correct |
5 |
Correct |
6 ms |
19980 KB |
Output is correct |
6 |
Correct |
4 ms |
19980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
19980 KB |
Output is correct |
2 |
Correct |
0 ms |
19980 KB |
Output is correct |
3 |
Correct |
0 ms |
19980 KB |
Output is correct |
4 |
Correct |
2 ms |
19980 KB |
Output is correct |
5 |
Correct |
2 ms |
19980 KB |
Output is correct |
6 |
Correct |
3 ms |
19980 KB |
Output is correct |
7 |
Correct |
0 ms |
19980 KB |
Output is correct |
8 |
Correct |
9 ms |
19980 KB |
Output is correct |
9 |
Correct |
3 ms |
19980 KB |
Output is correct |
10 |
Correct |
6 ms |
19980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
20252 KB |
Output is correct |
2 |
Correct |
100 ms |
20832 KB |
Output is correct |
3 |
Correct |
278 ms |
21600 KB |
Output is correct |
4 |
Correct |
308 ms |
23136 KB |
Output is correct |
5 |
Correct |
208 ms |
21600 KB |
Output is correct |
6 |
Correct |
358 ms |
23136 KB |
Output is correct |
7 |
Correct |
454 ms |
23136 KB |
Output is correct |
8 |
Correct |
434 ms |
23136 KB |
Output is correct |
9 |
Correct |
62 ms |
20448 KB |
Output is correct |
10 |
Correct |
222 ms |
21600 KB |
Output is correct |
11 |
Correct |
409 ms |
23136 KB |
Output is correct |
12 |
Correct |
511 ms |
23136 KB |
Output is correct |
13 |
Correct |
412 ms |
23136 KB |
Output is correct |
14 |
Correct |
393 ms |
23136 KB |
Output is correct |