oj.uz

Submission #76344

# Submission time Handle Problem Language Result Execution time Memory
76344 2018-09-12T20:37:02 Z Vasiljko Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 207048 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18+10;
const int N = 1e5+5;

ll n;
int m;
ll a[N],b[N],c[N],d[N],dpl[N],dpr[N];

struct node{
    ll t;
    node *L,*R;
    node(){
        t=INF;
        L=nullptr;
        R=nullptr;
    }
}*root;

void Set(node *cur,ll ss,ll se,ll ind,ll val){
    if(ss==se){
        cur->t=min(cur->t,val);
        return;
    }
    ll mid=(ss+se)>>1LL;
    if(ind<=mid){
        if(cur->L==nullptr)cur->L=new node();
        Set(cur->L,ss,mid,ind,val);
        cur->t=min(cur->t,cur->L->t);
    }
    else{
        if(cur->R==nullptr)cur->R=new node();
        Set(cur->R,mid+1LL,se,ind,val);
        cur->t=min(cur->t,cur->R->t);
    }
}

ll Get(node *cur,ll ss,ll se,ll qs,ll qe){
    if(qs>se||qe<ss||ss>se)return INF;
    if(qs<=ss&&se<=qe)return cur->t;

    ll mid=(ss+se)>>1LL;

    if(cur->L==nullptr)cur->L=new node();
    if(cur->R==nullptr)cur->R=new node();

    return min(Get(cur->L,ss,mid,qs,qe),Get(cur->R,mid+1,se,qs,qe));
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    root=new node();
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }

    ll ans=2*INF;

    for(int i=1;i<=m;i++){
        if(a[i]==1){
            dpl[i]=d[i];
            Set(root,1,n,c[i],dpl[i]);
        }else{
            dpl[i]=INF;
            dpl[i]=min(dpl[i],d[i]+Get(root,1,n,a[i],b[i]));
            Set(root,1,n,c[i],dpl[i]);
        }
    }

    root = new node();
    for(int i=1;i<=m;i++){
        if(b[i]==n){
            dpr[i]=d[i];
            Set(root,1,n,c[i],dpr[i]);
        }else{
            dpr[i]=INF;
            dpr[i]=min(dpr[i],d[i]+Get(root,1,n,a[i],b[i]));
            Set(root,1,n,c[i],dpr[i]);
        }
    }

    for(int i=1;i<=m;i++)ans=min(ans,dpl[i]+dpr[i]-d[i]);
    if(ans==INF)ans=-1;

    cout<<ans;
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 3 ms 1096 KB Output is correct
10 Correct 3 ms 1264 KB Output is correct
11 Correct 3 ms 1480 KB Output is correct
12 Correct 4 ms 2080 KB Output is correct
13 Correct 4 ms 2232 KB Output is correct
14 Correct 5 ms 2368 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 3 ms 1096 KB Output is correct
10 Correct 3 ms 1264 KB Output is correct
11 Correct 3 ms 1480 KB Output is correct
12 Correct 4 ms 2080 KB Output is correct
13 Correct 4 ms 2232 KB Output is correct
14 Correct 5 ms 2368 KB Output is correct
15 Correct 3 ms 2368 KB Output is correct
16 Correct 4 ms 2368 KB Output is correct
17 Correct 9 ms 3436 KB Output is correct
18 Correct 4 ms 3436 KB Output is correct
19 Correct 13 ms 6076 KB Output is correct
20 Correct 8 ms 6076 KB Output is correct
21 Correct 6 ms 6076 KB Output is correct
22 Correct 13 ms 6076 KB Output is correct
23 Correct 16 ms 6724 KB Output is correct
24 Correct 14 ms 6892 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 692 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 808 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 3 ms 1096 KB Output is correct
10 Correct 3 ms 1264 KB Output is correct
11 Correct 3 ms 1480 KB Output is correct
12 Correct 4 ms 2080 KB Output is correct
13 Correct 4 ms 2232 KB Output is correct
14 Correct 5 ms 2368 KB Output is correct
15 Correct 3 ms 2368 KB Output is correct
16 Correct 4 ms 2368 KB Output is correct
17 Correct 9 ms 3436 KB Output is correct
18 Correct 4 ms 3436 KB Output is correct
19 Correct 13 ms 6076 KB Output is correct
20 Correct 8 ms 6076 KB Output is correct
21 Correct 6 ms 6076 KB Output is correct
22 Correct 13 ms 6076 KB Output is correct
23 Correct 16 ms 6724 KB Output is correct
24 Correct 14 ms 6892 KB Output is correct
25 Correct 43 ms 11028 KB Output is correct
26 Correct 209 ms 51656 KB Output is correct
27 Correct 571 ms 93776 KB Output is correct
28 Correct 320 ms 93776 KB Output is correct
29 Correct 505 ms 113784 KB Output is correct
30 Correct 515 ms 113784 KB Output is correct
31 Execution timed out 1068 ms 207048 KB Time limit exceeded
32 Halted 0 ms 0 KB -