oj.uz

Submission #993452

# Submission time Handle Problem Language Result Execution time Memory
993452 2024-06-05T16:54:57 Z MarwenElarbi Event Hopping (BOI22_events) C++17
20 / 100
 291 ms 20980 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[s].se>=tab[e].fi&&tab[s].fi<=tab[e].fi){
            cout <<1<<endl;
            continue;
        }else if(tab[s].fi>=tab[e].fi&&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 1 ms 348 KB Output is correct
2 Correct 236 ms 19896 KB Output is correct
3 Correct 243 ms 19972 KB Output is correct
4 Correct 291 ms 19984 KB Output is correct
5 Correct 260 ms 20136 KB Output is correct
6 Correct 253 ms 20928 KB Output is correct
7 Incorrect 257 ms 20980 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 265 ms 20224 KB Output is correct
2 Correct 259 ms 20584 KB Output is correct
3 Correct 260 ms 19900 KB Output is correct
4 Correct 237 ms 20432 KB Output is correct
5 Correct 254 ms 20660 KB Output is correct
6 Correct 277 ms 20536 KB Output is correct
7 Correct 262 ms 20028 KB Output is correct
8 Correct 262 ms 20416 KB Output is correct
9 Correct 102 ms 19896 KB Output is correct
10 Correct 272 ms 20008 KB Output is correct
11 Correct 244 ms 19832 KB Output is correct
12 Correct 260 ms 19640 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 236 ms 19896 KB Output is correct
3 Correct 243 ms 19972 KB Output is correct
4 Correct 291 ms 19984 KB Output is correct
5 Correct 260 ms 20136 KB Output is correct
6 Correct 253 ms 20928 KB Output is correct
7 Incorrect 257 ms 20980 KB Output isn't correct
8 Halted 0 ms 0 KB -