oj.uz

Submission #997089

# Submission time Handle Problem Language Result Execution time Memory
997089 2024-06-11T17:23:57 Z MarwenElarbi Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> cor;
ll segtree[nax*4][2];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos][0]=1e18;
        segtree[pos][1]=1e18;
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
    segtree[pos][1]=min(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    return;
}
void update1(int pos,int l,int r,int index,ll value){
    if(l==r){
        segtree[pos][0]=min(segtree[pos][0],value);
        return;
    }
    int mid=(r+l)/2;
    if(index<=mid) update1(pos*2+1,l,mid,index,value);
    else update1(pos*2+2,mid+1,r,index,value);
    segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
    return;
}
void update2(int pos,int l,int r,int index,ll value){
    if(l==r){
        segtree[pos][1]=min(segtree[pos][1],value);
        return;
    }
    int mid=(r+l)/2;
    if(index<=mid) update2(pos*2+1,l,mid,index,value);
    else update2(pos*2+2,mid+1,r,index,value);
    segtree[pos][1]=min(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    return;
}
ll query1(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 1e18;
    else if(l>=left&&r<=right) return segtree[pos][0];
    int mid=(r+l)/2;
    return min(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
ll query2(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return 1e18;
    else if(l>=left&&r<=right) return segtree[pos][1];
    int mid=(r+l)/2;
    return min(query2(pos*2+1,l,mid,left,right),query2(pos*2+2,mid+1,r,left,right));
}
int main(){
    int n,m;
    cin>>n>>m;
    ll a[n],b[n],c[n],d[n];
    set<int> st;
    st.insert(1);
    st.insert(m);
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        st.insert(a[i]);
        st.insert(b[i]);
        st.insert(c[i]);
    }
    for(auto u:st) {
        cor.pb(u);
    }
    build(0,0,cor.size()-1);
    update1(0,0,cor.size()-1,0,0);
    update2(0,0,cor.size()-1,cor.size()-1,0);
    ll ans[cor.size()][2];
    for (int i = 0; i < cor.size(); ++i)
    {
        ans[i][0]=ans[i][1]=1e18;
    }
    ll res=1e18;
    for (int i = 0; i < n; ++i)
    {
        int l=lower_bound(cor.begin(),cor.end(),a[i])-cor.begin();
        int r=lower_bound(cor.begin(),cor.end(),b[i])-cor.begin();
        int cur=lower_bound(cor.begin(),cor.end(),c[i])-cor.begin();
        //cout <<l<<" "<<r<<" "<<cur<<endl;
        if(a[i]==1){
            ans[cur][0]=min(ans[cur][0],d[i]);
        }
        if(b[i]==m){
            ans[cur][1]=min(ans[cur][1],d[i]);
        }
        ll left=query1(0,0,cor.size()-1,l,r);
        ll right=query2(0,0,cor.size()-1,l,r);
        //cout <<left<<" "<<right<<" "<<d[i]<<endl;
        //cout <<ans[cur][0]<<" "<<ans[cur][1]<<" "<<d[i]<<endl;
        ans[cur][0]=min(ans[cur][0],d[i]+left);
        ans[cur][1]=min(ans[cur][1],d[i]+right);
        update1(0,0,cor.size()-1,cur,ans[cur][0]);
        update2(0,0,cor.size()-1,cur,ans[cur][1]);
        //cout <<ans[cur][0]<<" "<<ans[cur][1]<<" "<<d[i]<<endl;
        res=min(res,ans[cur][0]+ans[cur][1]-d[i]);
        //cout <<res<<endl;
    }
    if(res>=1e17) cout <<-1<<endl;
    else cout <<res<<endl;
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -