# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52531 |
2018-06-26T06:52:11 Z |
tlwpdus(#1968) |
Pinball (JOI14_pinball) |
C++11 |
|
10 ms |
8884 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll INF = 1LL<<55;
struct segtree {
int key = 524288;
ll tree[1050000];
void init() {
int i;
for (i=0;i<2*key;i++) tree[i] = INF;
}
void upd(int idx, ll v) {
idx += key;
while(idx) {
tree[idx] = min(tree[idx],v);
idx/=2;
}
}
ll getv(int s, int e) {
s += key; e += key;
ll val = INF;
while(s<=e) {
if (s&1) val = min(val,tree[s++]);
if (~e&1) val = min(val,tree[e--]);
s/=2; e/=2;
}
return val;
}
} st;
int m, n;
ll A[100100], B[100100], C[100100], D[100100], L[100100], R[100100];
vector<ll> comp;
int main() {
int i;
scanf("%d%d",&m,&n);
for (i=0;i<m;i++) scanf("%lld%lld%lld%lld",&A[i],&B[i],&C[i],&D[i]);
for (i=0;i<m;i++) {
comp.push_back(A[i]);
comp.push_back(B[i]);
comp.push_back(C[i]);
}
comp.push_back(1); comp.push_back(n);
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
for (i=0;i<m;i++) {
A[i] = lower_bound(comp.begin(),comp.end(),A[i])-comp.begin();
B[i] = lower_bound(comp.begin(),comp.end(),B[i])-comp.begin();
C[i] = lower_bound(comp.begin(),comp.end(),C[i])-comp.begin();
}
st.init();
st.upd(0,0);
for (i=0;i<m;i++) st.upd(C[i],L[i] = st.getv(A[i],B[i])+D[i]);
st.init();
st.upd((int)comp.size()-1,0);
for (i=0;i<m;i++) st.upd(C[i],R[i] = st.getv(A[i],B[i])+D[i]);
ll res = INF;
for (i=0;i<m;i++) res = min(res,L[i]+R[i]-D[i]);
printf("%lld\n",res);
return 0;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&m,&n);
~~~~~^~~~~~~~~~~~~~
pinball.cpp:44:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i=0;i<m;i++) scanf("%lld%lld%lld%lld",&A[i],&B[i],&C[i],&D[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
10 ms |
8756 KB |
Output is correct |
4 |
Correct |
10 ms |
8756 KB |
Output is correct |
5 |
Correct |
9 ms |
8756 KB |
Output is correct |
6 |
Correct |
10 ms |
8884 KB |
Output is correct |
7 |
Incorrect |
10 ms |
8884 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
10 ms |
8756 KB |
Output is correct |
4 |
Correct |
10 ms |
8756 KB |
Output is correct |
5 |
Correct |
9 ms |
8756 KB |
Output is correct |
6 |
Correct |
10 ms |
8884 KB |
Output is correct |
7 |
Incorrect |
10 ms |
8884 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
10 ms |
8756 KB |
Output is correct |
4 |
Correct |
10 ms |
8756 KB |
Output is correct |
5 |
Correct |
9 ms |
8756 KB |
Output is correct |
6 |
Correct |
10 ms |
8884 KB |
Output is correct |
7 |
Incorrect |
10 ms |
8884 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8568 KB |
Output is correct |
2 |
Correct |
10 ms |
8568 KB |
Output is correct |
3 |
Correct |
10 ms |
8756 KB |
Output is correct |
4 |
Correct |
10 ms |
8756 KB |
Output is correct |
5 |
Correct |
9 ms |
8756 KB |
Output is correct |
6 |
Correct |
10 ms |
8884 KB |
Output is correct |
7 |
Incorrect |
10 ms |
8884 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |