Submission #13701

#	Time	Username	Problem	Language	Result	Execution time	Memory
13701		dohyun0324	Pinball (JOI14_pinball)	C++98	100 / 100	246 ms	24132 KiB

pinball

#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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49