oj.uz

Submission #897708

# Submission time Handle Problem Language Result Execution time Memory
897708 2024-01-03T15:26:36 Z Aiperiii Pinball (JOI14_pinball) C++14
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=3e5+5;
int l[N*4],r[N*4];
void build(int v,int tl,int tr){
    if(tl==tr){
        l[v]=1e16;
        r[v]=1e16;
    }
    else{
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        l[v]=min(l[v*2],l[v*2+1]);
        r[v]=min(r[v*2],r[v*2+1]);
    }
}
int get_min_l(int v,int tl,int tr,int L,int R){
    if(tr<L or R<tl)return 1e18;
    if(L<=tl && tr<=R)return l[v];
    int tm=(tl+tr)/2;
    return min(get_min_l(v*2,tl,tm,L,R), get_min_l(v*2+1,tm+1,tr,L,R));
}
int get_min_r(int v,int tl,int tr,int L,int R){
    if(tr<L or R<tl)return 1e18;
    if(L<=tl && tr<=R)return r[v];
    int tm=(tl+tr)/2;
    return min(get_min_r(v*2,tl,tm,L,R), get_min_r(v*2+1,tm+1,tr,L,R));
}
void update_l(int v,int tl,int tr,int pos,int val){
    if(tl==tr)l[v]=min(val,l[v]);
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm)update_l(v*2,tl,tm,pos,val);
        else update_l(v*2+1,tm+1,tr,pos,val);
        l[v]=min(l[v*2],l[v*2+1]);
    }
}
void update_r(int v,int tl,int tr,int pos,int val){
    if(tl==tr)r[v]=min(val,r[v]);
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm)update_r(v*2,tl,tm,pos,val);
        else update_r(v*2+1,tm+1,tr,pos,val);
        r[v]=min(r[v*2],r[v*2+1]);
    }
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int m,T;
    cin>>m>>T;
    vector <int> a(m),b(m),c(m),d(m);
    vector <int> uni;
    uni.pb(1);uni.pb(T);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        uni.pb(c[i]);
    }
    int cnt=1;
    sort(all(uni));
    unordered_map <int,int> val_ind;
    val_ind[1]=cnt;
    for(int i=1;i<uni.size();i++){
        if(uni[i]!=uni[i-1]){
            cnt++;
            val_ind[uni[i]]=cnt;
        }
    }
    
    int n=cnt;
    build(1,1,n);
    
    int ans=1e16;
    for(int i=0;i<m;i++){
        int res=0;
        if(a[i]==1){
            res+=d[i];
            update_l(1,1,n,val_ind[c[i]],d[i]);
        }
        else{
            int x=get_min_l(1,1,n,val_ind[a[i]],val_ind[b[i]]);
            res+=x;res+=d[i];
            update_l(1,1,n,val_ind[c[i]],x+d[i]);
        }
        if(b[i]==T){
            res+=d[i];
            update_r(1,1,n,val_ind[c[i]],d[i]);
        }
        else{
            int x=get_min_r(1,1,n,val_ind[a[i]],val_ind[b[i]]);
            res+=x;res+=d[i];
            update_r(1,1,n,val_ind[c[i]],x+d[i]);
        }
        ans=min(ans,res-d[i]);
    }
    if(ans==1e16)ans=-1;
    cout<<ans<<"\n";
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:69:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=1;i<uni.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -