oj.uz

Submission #13701

# Submission time Handle Problem Language Result Execution time Memory
13701 2015-03-06T18:00:12 Z dohyun0324 Pinball (JOI14_pinball) C++
100 / 100
 246 ms 24132 KB 
#include<stdio.h>
#include<algorithm>
#define M 2147483647000000000LL
using namespace std;
int cnt,t,w,m,n,c[100010],a[100010],b[100010];
long long dap=M,d[100010],l[1200010],r[1200010],k1,k2;
struct data2{
    int x,y;
    bool operator<(const data2&r)const{
        return x<r.x;
    }
}arr[300010];
void updatel(int p,long long x){
    p+=(t-1); l[p]=min(l[p],x); p/=2;
    while(p){
        l[p]=min(l[p*2],l[p*2+1]);
        p/=2;
    }
}
void updater(int p,long long x){
    p+=(t-1); r[p]=min(r[p],x); p/=2;
    while(p){
        r[p]=min(r[p*2],r[p*2+1]);
        p/=2;
    }
}
long long queryl(int x,int y,int k,int s,int e){
    if(x>e || y<s) return M;
    if(s<=x && y<=e) return l[k];
    return min(queryl(x,(x+y)/2,k*2,s,e),queryl((x+y)/2+1,y,k*2+1,s,e));
}
long long queryr(int x,int y,int k,int s,int e){
    if(x>e || y<s) return M;
    if(s<=x && y<=e) return r[k];
    return min(queryr(x,(x+y)/2,k*2,s,e),queryr((x+y)/2+1,y,k*2+1,s,e));
}
int main()
{
    int i,st;
    scanf("%d %d",&m,&n);
    arr[++w].x=n; arr[w].y=0; arr[++w].x=1; arr[w].y=-1;
    for(i=1;i<=m;i++){
        scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]);
        arr[++w].x=a[i]; arr[w].y=i*3-2; arr[++w].x=b[i]; arr[w].y=i*3-1; arr[++w].x=c[i]; arr[w].y=i*3;
    }
    sort(arr+1,arr+w+1);
    for(i=1;i<=w;i++){
        if(arr[i].x!=arr[i-1].x) cnt++;
        if(arr[i].y==0) n=cnt;
        else if(arr[i].y==-1) st=cnt;
        else if(arr[i].y%3==1) a[arr[i].y/3+1]=cnt;
        else if(arr[i].y%3==2) b[arr[i].y/3+1]=cnt;
        else c[arr[i].y/3]=cnt;
    }
    for(t=1;t<=cnt;t*=2);
    for(i=1;i<=t*2;i++) l[i]=r[i]=M;
    updatel(st,0); updater(n,0);
    for(i=1;i<=m;i++){
        k1=queryl(1,t,1,a[i],b[i])+d[i];
        k2=queryr(1,t,1,a[i],b[i])+d[i];
        if(dap>k1+k2-d[i]) dap=k1+k2-d[i];
        updatel(c[i],k1);
        updater(c[i],k2);
    }
    if(dap>2147483647000000LL) printf("-1");
    else printf("%lld",dap);
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24132 KB Output is correct
2 Correct 0 ms 24132 KB Output is correct
3 Correct 0 ms 24132 KB Output is correct
4 Correct 0 ms 24132 KB Output is correct
5 Correct 0 ms 24132 KB Output is correct
6 Correct 0 ms 24132 KB Output is correct
7 Correct 0 ms 24132 KB Output is correct
8 Correct 0 ms 24132 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24132 KB Output is correct
2 Correct 0 ms 24132 KB Output is correct
3 Correct 0 ms 24132 KB Output is correct
4 Correct 0 ms 24132 KB Output is correct
5 Correct 0 ms 24132 KB Output is correct
6 Correct 0 ms 24132 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24132 KB Output is correct
2 Correct 0 ms 24132 KB Output is correct
3 Correct 0 ms 24132 KB Output is correct
4 Correct 2 ms 24132 KB Output is correct
5 Correct 0 ms 24132 KB Output is correct
6 Correct 0 ms 24132 KB Output is correct
7 Correct 2 ms 24132 KB Output is correct
8 Correct 3 ms 24132 KB Output is correct
9 Correct 3 ms 24132 KB Output is correct
10 Correct 0 ms 24132 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24132 KB Output is correct
2 Correct 56 ms 24132 KB Output is correct
3 Correct 145 ms 24132 KB Output is correct
4 Correct 133 ms 24132 KB Output is correct
5 Correct 103 ms 24132 KB Output is correct
6 Correct 176 ms 24132 KB Output is correct
7 Correct 246 ms 24132 KB Output is correct
8 Correct 225 ms 24132 KB Output is correct
9 Correct 37 ms 24132 KB Output is correct
10 Correct 103 ms 24132 KB Output is correct
11 Correct 193 ms 24132 KB Output is correct
12 Correct 230 ms 24132 KB Output is correct
13 Correct 215 ms 24132 KB Output is correct
14 Correct 224 ms 24132 KB Output is correct