| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 109184 |
2019-05-05T11:16:45 Z |
maruii |
Pinball (JOI14_pinball) |
C++14 |
|
213 ms |
23656 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SIZE = 1<<19;
struct ST{
ll data[2*SIZE];
void init(){fill(data, data+2*SIZE, 1e18);}
void update(int x, ll v){
for(x+=SIZE; x; x>>=1) data[x] = min(data[x], v);
}
ll query(int s, int e){
ll ret = 1e18;
for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
if( s&1) ret = min(ret, data[s++]);
if(~e&1) ret = min(ret, data[e--]);
}
return ret;
}
} seg1, seg2;
int A[100000], B[100000], C[100000], D[100000];
vector<int> xx;
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int M, N; cin>>M>>N;
for(int i=0; i<M; ++i){
cin>>A[i]>>B[i]>>C[i]>>D[i];
xx.push_back(A[i]), xx.push_back(B[i]), xx.push_back(C[i]);
}
xx.push_back(1), xx.push_back(N);
sort(xx.begin(), xx.end()), xx.erase(unique(xx.begin(), xx.end()), xx.end());
for(int i=0; i<M; ++i){
A[i] = lower_bound(xx.begin(), xx.end(), A[i]) - xx.begin();
B[i] = lower_bound(xx.begin(), xx.end(), B[i]) - xx.begin();
C[i] = lower_bound(xx.begin(), xx.end(), C[i]) - xx.begin();
}
seg1.init(), seg2.init(), seg1.update(0, 0), seg2.update(xx.size()-1, 0);
long long ans = 1e18;
for(int i=0; i<M; ++i){
ll s = seg1.query(A[i], B[i]), t = seg2.query(A[i], B[i]);
if(seg1.query(C[i], C[i]) > D[i] + s) seg1.update(C[i], D[i] + s);
if(seg2.query(C[i], C[i]) > D[i] + t) seg2.update(C[i], D[i] + t);
ans = min(ans, D[i] + s + t);
}
if(ans == 1e18) ans = -1;
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 3 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
16640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 3 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
16640 KB |
Output is correct |
| 9 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 10 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 11 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 12 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 13 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 14 |
Correct |
15 ms |
16768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 3 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
16640 KB |
Output is correct |
| 9 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 10 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 11 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 12 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 13 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 14 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 15 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 16 |
Correct |
19 ms |
16796 KB |
Output is correct |
| 17 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 18 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 19 |
Correct |
16 ms |
16888 KB |
Output is correct |
| 20 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 21 |
Correct |
15 ms |
16748 KB |
Output is correct |
| 22 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 23 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 24 |
Correct |
18 ms |
16896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 3 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 4 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 5 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 6 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 7 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 8 |
Correct |
14 ms |
16640 KB |
Output is correct |
| 9 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 10 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 11 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 12 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 13 |
Correct |
14 ms |
16768 KB |
Output is correct |
| 14 |
Correct |
15 ms |
16768 KB |
Output is correct |
| 15 |
Correct |
16 ms |
16768 KB |
Output is correct |
| 16 |
Correct |
19 ms |
16796 KB |
Output is correct |
| 17 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 18 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 19 |
Correct |
16 ms |
16888 KB |
Output is correct |
| 20 |
Correct |
16 ms |
16896 KB |
Output is correct |
| 21 |
Correct |
15 ms |
16748 KB |
Output is correct |
| 22 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 23 |
Correct |
17 ms |
16896 KB |
Output is correct |
| 24 |
Correct |
18 ms |
16896 KB |
Output is correct |
| 25 |
Correct |
32 ms |
17528 KB |
Output is correct |
| 26 |
Correct |
79 ms |
18476 KB |
Output is correct |
| 27 |
Correct |
116 ms |
21332 KB |
Output is correct |
| 28 |
Correct |
157 ms |
23396 KB |
Output is correct |
| 29 |
Correct |
101 ms |
20204 KB |
Output is correct |
| 30 |
Correct |
144 ms |
23504 KB |
Output is correct |
| 31 |
Correct |
213 ms |
23532 KB |
Output is correct |
| 32 |
Correct |
197 ms |
23656 KB |
Output is correct |
| 33 |
Correct |
36 ms |
18040 KB |
Output is correct |
| 34 |
Correct |
93 ms |
20224 KB |
Output is correct |
| 35 |
Correct |
122 ms |
23528 KB |
Output is correct |
| 36 |
Correct |
189 ms |
23400 KB |
Output is correct |
| 37 |
Correct |
170 ms |
23628 KB |
Output is correct |
| 38 |
Correct |
161 ms |
23512 KB |
Output is correct |
