oj.uz

Submission #993462

# Submission time Handle Problem Language Result Execution time Memory
993462 2024-06-05T17:11:05 Z MarwenElarbi Event Hopping (BOI22_events) C++17
20 / 100
 290 ms 20804 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=3e5+5;
pair<int,int> segtree[4*nax];
struct query{
    int x,type,idx,value;
};
bool compare(query a,query b){
    if(a.x!=b.x) return a.x<b.x;
    else if(a.type!=b.type) return a.type<b.type;
    else return a.idx<b.idx;
}
vector<query> sweep;
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]={sweep[l].value,sweep[l].idx};
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);
    return;
}
pair<int,int> query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return {1e9,1e9};
    else if(l>=left&&r<=right) {
        return segtree[pos];
    }
    int mid=(r+l)/2;
    return min(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
int main(){
    int n,q;
    cin>>n>>q;
    for (int i = 0; i < n*2*4; ++i)
    {
        segtree[i]={1e9,1e9};
    }
    vector<pair<int,int>> tab(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i].fi>>tab[i].se;
        sweep.pb({tab[i].fi,0,i,tab[i].fi});
        sweep.pb({tab[i].se,1,i,tab[i].fi});
    }
    sort(sweep.begin(),sweep.end(),compare);
    pair<int,int> pos[n];
    for (int i = 0; i < sweep.size(); ++i)
    {
        if(sweep[i].type==0){
            pos[sweep[i].idx].fi=i;
        }else{
            pos[sweep[i].idx].se=i;
        }
    }
    build(0,0,sweep.size()-1);
    int dp[n][20];
    for (int i = 0; i < sweep.size(); ++i)
    {
        if(sweep[i].type==0){
            dp[sweep[i].idx][0]=query(0,0,sweep.size()-1,pos[sweep[i].idx].fi,pos[sweep[i].idx].se).se;
        }
    }
    for (int j = 1; j < 20; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            dp[i][j]=dp[dp[i][j-1]][j-1];
        }
    }
    while(q--){
        int s,e;
        cin>>s>>e;
        s--;
        e--;
        int ans=0;
        if(s==e){
            cout <<0<<endl;
            continue;
        }else if(tab[s].fi==tab[e].fi&&tab[s].se==tab[e].se){
            cout <<1<<endl;
            continue;
        }else if(tab[e].se<tab[s].se){
            cout <<"impossible"<<endl;
            continue;
        }else if(tab[e].fi<=tab[s].se&&tab[s].se<=tab[e].se){
            cout <<1<<endl;
            continue;
        }
        for (int i = 19; i >= 0; --i)
        {
            if(tab[dp[e][i]].fi>tab[s].se){
                ans+=(1<<i);
                e=dp[e][i];
            }
        }
        //cout <<"hey "<<e<<" "<<ans<<endl;
        if(tab[dp[e][0]].fi>tab[s].se){
            cout <<"impossible"<<endl;
            continue;
        } else cout <<ans+2<<endl;
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 255 ms 20564 KB Output is correct
3 Correct 248 ms 19960 KB Output is correct
4 Correct 261 ms 19932 KB Output is correct
5 Correct 248 ms 20276 KB Output is correct
6 Correct 247 ms 19896 KB Output is correct
7 Incorrect 246 ms 20088 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.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 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.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 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.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 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 19896 KB Output is correct
2 Correct 249 ms 19900 KB Output is correct
3 Correct 254 ms 20804 KB Output is correct
4 Correct 229 ms 20408 KB Output is correct
5 Correct 254 ms 20196 KB Output is correct
6 Correct 290 ms 20004 KB Output is correct
7 Correct 266 ms 20152 KB Output is correct
8 Correct 249 ms 20668 KB Output is correct
9 Correct 101 ms 20152 KB Output is correct
10 Correct 266 ms 20412 KB Output is correct
11 Correct 240 ms 19592 KB Output is correct
12 Correct 255 ms 19640 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 255 ms 20564 KB Output is correct
3 Correct 248 ms 19960 KB Output is correct
4 Correct 261 ms 19932 KB Output is correct
5 Correct 248 ms 20276 KB Output is correct
6 Correct 247 ms 19896 KB Output is correct
7 Incorrect 246 ms 20088 KB Output isn't correct
8 Halted 0 ms 0 KB -