oj.uz

Submission #997126

# Submission time Handle Problem Language Result Execution time Memory
997126 2024-06-11T17:52:13 Z MarwenElarbi Pinball (JOI14_pinball) C++17
51 / 100
 324 ms 67060 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],d[i]);
        }
        if(b[i]==m){
            ans[cur][1]=min(ans[cur][1]+d[i],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],d[i]+left);
        ans[cur][1]=min(ans[cur][1]+d[i],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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 2 ms 600 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 3 ms 720 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 856 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 452 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 2 ms 600 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 3 ms 720 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 856 KB Output is correct
25 Correct 29 ms 4416 KB Output is correct
26 Correct 77 ms 8020 KB Output is correct
27 Correct 192 ms 16072 KB Output is correct
28 Correct 169 ms 7504 KB Output is correct
29 Correct 142 ms 14284 KB Output is correct
30 Correct 213 ms 10836 KB Output is correct
31 Correct 324 ms 27088 KB Output is correct
32 Correct 277 ms 19660 KB Output is correct
33 Correct 42 ms 7900 KB Output is correct
34 Correct 147 ms 22212 KB Output is correct
35 Runtime error 178 ms 67060 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -