| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 25308 |
2017-06-21T06:27:25 Z |
김동현(#1058) |
Pinball (JOI14_pinball) |
C++14 |
|
299 ms |
21136 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int n, m, s[100010], e[100010], x[100010], c[100010], xx[300010];
ll ans = inf;
int cp(int x){ return (int)(lower_bound(xx + 1, xx + 3 * m + 3, x) - xx); }
const int sz = 524288;
struct Seg{
ll dat[2 * sz];
void ini(){ fill(dat + 1, dat + 2 * sz, inf); }
void upd(int x, ll v){
x += sz - 1; dat[x] = min(dat[x], v);
for(x /= 2; x; x /= 2) dat[x] = min(dat[2 * x], dat[2 * x + 1]);
}
ll get(int s, int e){
ll ret = inf;
for(s += sz - 1, e += sz - 1; s <= e; s /= 2, e /= 2){
if(s % 2 == 1) ret = min(ret, dat[s++]);
if(e % 2 == 0) ret = min(ret, dat[e--]);
}
return ret;
}
} LS, RS;
int main(){
scanf("%d%d", &m, &n);
for(int i = 0; i < m; i++){
scanf("%d%d%d%d", s + i, e + i, x + i, c + i);
xx[3 * i + 1] = s[i];
xx[3 * i + 2] = e[i];
xx[3 * i + 3] = x[i];
}
xx[3 * m + 1] = 1;
xx[3 * m + 2] = n;
sort(xx + 1, xx + 3 * m + 3);
LS.ini(); RS.ini();
LS.upd(cp(1), 0); RS.upd(cp(n), 0);
for(int i = 0; i < m; i++){
s[i] = cp(s[i]); e[i] = cp(e[i]); x[i] = cp(x[i]);
ll lv = LS.get(s[i], e[i]), rv = RS.get(s[i], e[i]);
ans = min(ans, lv + rv + c[i]);
LS.upd(x[i], lv + c[i]);
RS.upd(x[i], rv + c[i]);
}
printf("%lld\n", ans > (inf / 10 * 9) ? -1 : ans);
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:30:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &m, &n);
^
pinball.cpp:32:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", s + i, e + i, x + i, c + i);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
6 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
3 ms |
21136 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
6 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
0 ms |
21136 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
0 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
6 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
6 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
6 ms |
21136 KB |
Output is correct |
| 9 |
Correct |
3 ms |
21136 KB |
Output is correct |
| 10 |
Correct |
6 ms |
21136 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
26 ms |
21136 KB |
Output is correct |
| 2 |
Correct |
56 ms |
21136 KB |
Output is correct |
| 3 |
Correct |
186 ms |
21136 KB |
Output is correct |
| 4 |
Correct |
243 ms |
21136 KB |
Output is correct |
| 5 |
Correct |
136 ms |
21136 KB |
Output is correct |
| 6 |
Correct |
246 ms |
21136 KB |
Output is correct |
| 7 |
Correct |
233 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
299 ms |
21136 KB |
Output is correct |
| 9 |
Correct |
36 ms |
21136 KB |
Output is correct |
| 10 |
Correct |
119 ms |
21136 KB |
Output is correct |
| 11 |
Correct |
176 ms |
21136 KB |
Output is correct |
| 12 |
Correct |
266 ms |
21136 KB |
Output is correct |
| 13 |
Correct |
176 ms |
21136 KB |
Output is correct |
| 14 |
Correct |
156 ms |
21136 KB |
Output is correct |
