# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52492 |
2018-06-26T05:58:58 Z |
김세빈(#1365) |
Pinball (JOI14_pinball) |
C++11 |
|
126 ms |
48204 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
ll l,r,c;
node() { l = r = 0, c = 1e18; }
};
node T[2][505050];
ll n,m,k,ans;
void insert(ll t, ll p, ll s, ll e, ll v, ll c)
{
T[t][p].c = min(T[t][p].c, c);
if(s == e) return;
ll mid = s+e >> 1;
if(v <= mid){
if(!T[t][p].l) T[t][p].l = ++k;
insert(t, T[t][p].l, s, mid, v, c);
}
else{
if(!T[t][p].r) T[t][p].r = ++k;
insert(t, T[t][p].r, mid+1, e, v, c);
}
}
ll find(ll t, ll p, ll s, ll e, ll l, ll r)
{
if(!p || e < l || r < s) return 1e18;
if(l <= s && e <= r) return T[t][p].c;
ll mid = s+e >> 1;
return min(find(t, T[t][p].l, s, mid, l, r), find(t, T[t][p].r, mid+1, e, l, r));
}
int main()
{
ll i,a,b,c,d,x,x1,x2;
ans = 1e18;
k = 1;
scanf("%lld%lld",&m,&n);
for(i=0;i<m;i++){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(a == 1 && b == n){
ans = min(ans, d);
}
else if(a == 1){
insert(0, 1, 1, 1e9, c, d);
x = find(1, 1, 1, 1e9, a, b);
if(x < 1e18) ans = min(ans, x + d);
}
else if(b == n){
insert(1, 1, 1, 1e9, c, d);
x = find(0, 1, 1, 1e9, a, b);
if(x < 1e18) ans = min(ans, x + d);
}
else{
x1 = find(0, 1, 1, 1e9, a, b);
x2 = find(1, 1, 1, 1e9, a, b);
if(x1 < 1e18) insert(0, 1, 1, 1e9, c, x1 + d);
if(x2 < 1e18) insert(1, 1, 1, 1e9, c, x2 + d);
if(x1 + x2 < 1e18) ans = min(ans, x1 + x2 + d);
}
}
printf("%lld\n",ans < 1e18? ans : -1);
return 0;
}
Compilation message
pinball.cpp: In function 'void insert(ll, ll, ll, ll, ll, ll)':
pinball.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
ll mid = s+e >> 1;
~^~
pinball.cpp: In function 'll find(ll, ll, ll, ll, ll, ll)':
pinball.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
ll mid = s+e >> 1;
~^~
pinball.cpp: In function 'int main()':
pinball.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&m,&n);
~~~~~^~~~~~~~~~~~~~~~~~
pinball.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
24056 KB |
Output is correct |
2 |
Correct |
20 ms |
24244 KB |
Output is correct |
3 |
Correct |
19 ms |
24244 KB |
Output is correct |
4 |
Correct |
19 ms |
24244 KB |
Output is correct |
5 |
Correct |
20 ms |
24244 KB |
Output is correct |
6 |
Correct |
19 ms |
24244 KB |
Output is correct |
7 |
Correct |
24 ms |
24244 KB |
Output is correct |
8 |
Correct |
21 ms |
24244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
24056 KB |
Output is correct |
2 |
Correct |
20 ms |
24244 KB |
Output is correct |
3 |
Correct |
19 ms |
24244 KB |
Output is correct |
4 |
Correct |
19 ms |
24244 KB |
Output is correct |
5 |
Correct |
20 ms |
24244 KB |
Output is correct |
6 |
Correct |
19 ms |
24244 KB |
Output is correct |
7 |
Correct |
24 ms |
24244 KB |
Output is correct |
8 |
Correct |
21 ms |
24244 KB |
Output is correct |
9 |
Correct |
19 ms |
24244 KB |
Output is correct |
10 |
Correct |
24 ms |
24244 KB |
Output is correct |
11 |
Correct |
23 ms |
24244 KB |
Output is correct |
12 |
Correct |
21 ms |
24244 KB |
Output is correct |
13 |
Correct |
20 ms |
24244 KB |
Output is correct |
14 |
Correct |
19 ms |
24244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
24056 KB |
Output is correct |
2 |
Correct |
20 ms |
24244 KB |
Output is correct |
3 |
Correct |
19 ms |
24244 KB |
Output is correct |
4 |
Correct |
19 ms |
24244 KB |
Output is correct |
5 |
Correct |
20 ms |
24244 KB |
Output is correct |
6 |
Correct |
19 ms |
24244 KB |
Output is correct |
7 |
Correct |
24 ms |
24244 KB |
Output is correct |
8 |
Correct |
21 ms |
24244 KB |
Output is correct |
9 |
Correct |
19 ms |
24244 KB |
Output is correct |
10 |
Correct |
24 ms |
24244 KB |
Output is correct |
11 |
Correct |
23 ms |
24244 KB |
Output is correct |
12 |
Correct |
21 ms |
24244 KB |
Output is correct |
13 |
Correct |
20 ms |
24244 KB |
Output is correct |
14 |
Correct |
19 ms |
24244 KB |
Output is correct |
15 |
Correct |
18 ms |
24368 KB |
Output is correct |
16 |
Correct |
19 ms |
24368 KB |
Output is correct |
17 |
Correct |
24 ms |
24368 KB |
Output is correct |
18 |
Correct |
23 ms |
24368 KB |
Output is correct |
19 |
Correct |
24 ms |
24368 KB |
Output is correct |
20 |
Correct |
21 ms |
24368 KB |
Output is correct |
21 |
Correct |
19 ms |
24368 KB |
Output is correct |
22 |
Correct |
22 ms |
24368 KB |
Output is correct |
23 |
Correct |
19 ms |
24368 KB |
Output is correct |
24 |
Correct |
20 ms |
24368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
24056 KB |
Output is correct |
2 |
Correct |
20 ms |
24244 KB |
Output is correct |
3 |
Correct |
19 ms |
24244 KB |
Output is correct |
4 |
Correct |
19 ms |
24244 KB |
Output is correct |
5 |
Correct |
20 ms |
24244 KB |
Output is correct |
6 |
Correct |
19 ms |
24244 KB |
Output is correct |
7 |
Correct |
24 ms |
24244 KB |
Output is correct |
8 |
Correct |
21 ms |
24244 KB |
Output is correct |
9 |
Correct |
19 ms |
24244 KB |
Output is correct |
10 |
Correct |
24 ms |
24244 KB |
Output is correct |
11 |
Correct |
23 ms |
24244 KB |
Output is correct |
12 |
Correct |
21 ms |
24244 KB |
Output is correct |
13 |
Correct |
20 ms |
24244 KB |
Output is correct |
14 |
Correct |
19 ms |
24244 KB |
Output is correct |
15 |
Correct |
18 ms |
24368 KB |
Output is correct |
16 |
Correct |
19 ms |
24368 KB |
Output is correct |
17 |
Correct |
24 ms |
24368 KB |
Output is correct |
18 |
Correct |
23 ms |
24368 KB |
Output is correct |
19 |
Correct |
24 ms |
24368 KB |
Output is correct |
20 |
Correct |
21 ms |
24368 KB |
Output is correct |
21 |
Correct |
19 ms |
24368 KB |
Output is correct |
22 |
Correct |
22 ms |
24368 KB |
Output is correct |
23 |
Correct |
19 ms |
24368 KB |
Output is correct |
24 |
Correct |
20 ms |
24368 KB |
Output is correct |
25 |
Correct |
39 ms |
24368 KB |
Output is correct |
26 |
Correct |
89 ms |
24368 KB |
Output is correct |
27 |
Runtime error |
126 ms |
48204 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
28 |
Halted |
0 ms |
0 KB |
- |