oj.uz

Submission #993165

# Submission time Handle Problem Language Result Execution time Memory
993165 2024-06-05T11:52:53 Z MarwenElarbi Event Hopping (BOI22_events) C++17
0 / 100
 341 ms 41132 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][2];
struct query{
    int x,type,idx,l1,r1;
};
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][0]={sweep[l].l1,sweep[l].idx};
        segtree[pos][1]={sweep[l].r1,sweep[l].idx};
        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]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
    return;
}
pair<int,int> query1(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][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));
}
pair<int,int> query2(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return {-1,-1};
    else if(l>=left&&r<=right) return segtree[pos][1];
    int mid=(r+l)/2;
    return max(query2(pos*2+1,l,mid,left,right),query2(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][0]={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,tab[i].se});
        sweep.pb({tab[i].se,1,i,tab[i].fi,tab[i].se});
    }
    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];
    int dp1[n][20];
    for (int i = 0; i < sweep.size(); ++i)
    {
        //cout <<query1(0,0,sweep.size()-1,pos[sweep[i].idx].fi,pos[sweep[i].idx].se).se<<endl;
        if(sweep[i].type==1){
            dp[sweep[i].idx][0]=query2(0,0,sweep.size()-1,0,pos[sweep[i].idx].se).se;
        }else{
            dp1[sweep[i].idx][0]=query1(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];
            dp1[i][j]=dp1[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].fi&&tab[e].fi<tab[s].fi){
            cout <<"impossible"<<endl;
            continue;
        }else if(tab[e].fi<=tab[s].fi&&tab[s].fi<=tab[e].se&&tab[e].se<=tab[s].se){
            cout <<"impossible"<<endl;
            continue;
        }else if(tab[s].se>=tab[e].fi&&tab[s].fi<=tab[e].fi){
            cout <<1<<endl;
            continue;
        }
        for (int i = 19; i >= 0; --i)
        {
            if(tab[dp[s][i]].se<tab[e].fi){
                ans+=(1<<i);
                s=dp[s][i];
            }
        }//cout <<"nab "<<s<<" "<<ans<<endl;
        if(tab[dp[s][0]].se<tab[e].fi){
            cout <<"impossible"<<endl;
            continue;
        }
        for (int i = 19; i >= 0; --i)
        {
            if(tab[dp1[e][i]].fi>tab[dp[s][i]].se){
                ans+=(1<<i);
                e=dp1[e][i];
            }
        }
        //cout <<s<<" "<<e<<endl;
        if(tab[dp1[e][0]].fi>tab[s].se) cout <<"impossible"<<endl;
        else if(tab[dp1[e][0]].fi==tab[s].se) cout <<ans+2<<endl;
        else cout <<ans+1<<endl;
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 289 ms 40180 KB Output is correct
3 Correct 322 ms 40860 KB Output is correct
4 Correct 320 ms 40332 KB Output is correct
5 Correct 314 ms 39864 KB Output is correct
6 Correct 320 ms 39604 KB Output is correct
7 Incorrect 341 ms 39580 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

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

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 40764 KB Output is correct
2 Correct 299 ms 39864 KB Output is correct
3 Correct 331 ms 40376 KB Output is correct
4 Correct 283 ms 41060 KB Output is correct
5 Correct 304 ms 40964 KB Output is correct
6 Incorrect 301 ms 41132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 289 ms 40180 KB Output is correct
3 Correct 322 ms 40860 KB Output is correct
4 Correct 320 ms 40332 KB Output is correct
5 Correct 314 ms 39864 KB Output is correct
6 Correct 320 ms 39604 KB Output is correct
7 Incorrect 341 ms 39580 KB Output isn't correct
8 Halted 0 ms 0 KB -