| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19178 |
2016-02-19T13:06:51 Z |
comet |
Pinball (JOI14_pinball) |
C++ |
|
202 ms |
24912 KB |
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
int N,M;
struct obs{
int L,R;
int G;
ll C;
}a[100010];
int lu[300010];
ll dp_L[100010],dp_R[100010];
void compress(){
lu[0]=1;
lu[1]=M;
M=2;
for(int i=0;i<N;i++){
lu[M++]=a[i].L;
lu[M++]=a[i].R;
lu[M++]=a[i].G;
}
sort(lu,lu+M);
M=unique(lu,lu+M)-lu;
for(int i=0;i<N;i++){
a[i].L=lower_bound(lu,lu+M,a[i].L)-lu;
a[i].R=lower_bound(lu,lu+M,a[i].R)-lu;
a[i].G=lower_bound(lu,lu+M,a[i].G)-lu;
}
}
void input(){
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++){
scanf("%d%d%d%lld",&a[i].L,&a[i].R,&a[i].G,&a[i].C);
}
}
ll tree_L[1200000],tree_R[1200000];
int sz;
void init(){
compress();
for(sz=1;sz<M;sz<<=1);
for(int i=0;i<=sz+M;i++){
tree_L[i]=tree_R[i]=1e18;
}
}
void update(ll tree[],int x,ll c){
x+=sz;
tree[x]=min(tree[x],c);
x>>=1;
while(x){
tree[x]=min(tree[x*2],tree[x*2+1]);
x>>=1;
}
}
ll query(ll tree[],int L,int R){
L+=sz,R+=sz;
ll ret=1e18;
while(L<R){
if(L&1)ret=min(ret,tree[L++]);
if(~R&1)ret=min(ret,tree[R--]);
L>>=1,R>>=1;
}
if(L==R){
ret=min(ret,tree[L]);
}
return ret;
}
void PS(){
init();
for(int i=0;i<N;i++){
dp_L[i]=dp_R[i]=1e18;
if(a[i].L==0){
dp_L[i]=a[i].C;
}
if(a[i].R==M-1){
dp_R[i]=a[i].C;
}
dp_L[i]=min(dp_L[i],query(tree_L,a[i].L,a[i].R)+a[i].C);
dp_R[i]=min(dp_R[i],query(tree_R,a[i].L,a[i].R)+a[i].C);
update(tree_L,a[i].G,dp_L[i]);
update(tree_R,a[i].G,dp_R[i]);
}
ll ans=1e18;
for(int i=0;i<N;i++){
ans=min(ans,dp_L[i]+dp_R[i]-a[i].C);
}
if(ans==1e18){
puts("-1");
}else{
printf("%lld\n",ans);
}
}
int main(){
input();
PS();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 5 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 6 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 7 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 8 |
Correct |
0 ms |
24912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 5 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 6 |
Correct |
0 ms |
24912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 2 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 3 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 4 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 5 |
Correct |
3 ms |
24912 KB |
Output is correct |
| 6 |
Correct |
2 ms |
24912 KB |
Output is correct |
| 7 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 8 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 9 |
Correct |
0 ms |
24912 KB |
Output is correct |
| 10 |
Correct |
0 ms |
24912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
24912 KB |
Output is correct |
| 2 |
Correct |
39 ms |
24912 KB |
Output is correct |
| 3 |
Correct |
125 ms |
24912 KB |
Output is correct |
| 4 |
Correct |
128 ms |
24912 KB |
Output is correct |
| 5 |
Correct |
88 ms |
24912 KB |
Output is correct |
| 6 |
Correct |
178 ms |
24912 KB |
Output is correct |
| 7 |
Correct |
202 ms |
24912 KB |
Output is correct |
| 8 |
Correct |
198 ms |
24912 KB |
Output is correct |
| 9 |
Correct |
29 ms |
24912 KB |
Output is correct |
| 10 |
Correct |
88 ms |
24912 KB |
Output is correct |
| 11 |
Correct |
130 ms |
24912 KB |
Output is correct |
| 12 |
Correct |
191 ms |
24912 KB |
Output is correct |
| 13 |
Correct |
168 ms |
24912 KB |
Output is correct |
| 14 |
Correct |
160 ms |
24912 KB |
Output is correct |
