oj.uz

Submission #13698

# Submission time Handle Problem Language Result Execution time Memory
13698 2015-03-06T17:56:06 Z dohyun0324 Pinball (JOI14_pinball) C++
51 / 100
 175 ms 10848 KB 
#include<stdio.h>
#include<algorithm>
#define M 2147483647000000000LL
using namespace std;
int cnt,t,w,m,n,c[100010],pos[200010],a[100010],b[100010];
long long dap=M,d[100010],l[300010],r[300010];
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;
    long long k1,k2;
    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>21474836470000LL) printf("-1");
    else printf("%lld",dap);
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10848 KB Output is correct
2 Correct 47 ms 10848 KB Output is correct
3 Correct 141 ms 10848 KB Output is correct
4 Correct 142 ms 10848 KB Output is correct
5 Correct 120 ms 10848 KB Output is correct
6 Correct 175 ms 10848 KB Output is correct
7 Incorrect 113 ms 10848 KB Output isn't correct
8 Halted 0 ms 0 KB -