oj.uz

Submission #993447

# Submission time Handle Problem Language Result Execution time Memory
993447 2024-06-05T16:43:45 Z MarwenElarbi Event Hopping (BOI22_events) C++17
20 / 100
 290 ms 23996 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].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;
        }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 0 ms 344 KB Output is correct
2 Correct 263 ms 23432 KB Output is correct
3 Correct 278 ms 22968 KB Output is correct
4 Correct 260 ms 23740 KB Output is correct
5 Correct 264 ms 23736 KB Output is correct
6 Correct 247 ms 22964 KB Output is correct
7 Incorrect 275 ms 23228 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 600 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 344 KB Output is correct
2 Correct 0 ms 600 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 344 KB Output is correct
2 Correct 0 ms 600 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 239 ms 23228 KB Output is correct
2 Correct 256 ms 23000 KB Output is correct
3 Correct 260 ms 22972 KB Output is correct
4 Correct 267 ms 23396 KB Output is correct
5 Correct 251 ms 23396 KB Output is correct
6 Correct 290 ms 23996 KB Output is correct
7 Correct 270 ms 23224 KB Output is correct
8 Correct 252 ms 23340 KB Output is correct
9 Correct 103 ms 21408 KB Output is correct
10 Correct 245 ms 22716 KB Output is correct
11 Correct 246 ms 22460 KB Output is correct
12 Correct 248 ms 22764 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 263 ms 23432 KB Output is correct
3 Correct 278 ms 22968 KB Output is correct
4 Correct 260 ms 23740 KB Output is correct
5 Correct 264 ms 23736 KB Output is correct
6 Correct 247 ms 22964 KB Output is correct
7 Incorrect 275 ms 23228 KB Output isn't correct
8 Halted 0 ms 0 KB -