oj.uz

Submission #993122

# Submission time Handle Problem Language Result Execution time Memory
993122 2024-06-05T10:31:45 Z MarwenElarbi Event Hopping (BOI22_events) C++17
20 / 100
 319 ms 23480 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;
vector<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]=max(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 {-1,-1};
    else if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    return max(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;
    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].se});
        sweep.pb({tab[i].se,1,i,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];
    for (int i = 0; i < sweep.size(); ++i)
    {
        if(sweep[i].type==1){
            dp[sweep[i].idx][0]=query(0,0,sweep.size()-1,0,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;
        }
        for (int i = 19; i >= 0; --i)
        {
            if(tab[dp[s][i]].se<tab[e].fi){
                ans+=(1<<i);
                s=dp[s][i];
            }
        }
        //cout <<s<<endl;
        if(tab[dp[s][0]].se<tab[e].fi) cout <<"impossible"<<endl;
        else if(tab[s].se<tab[e].fi) cout <<ans+2<<endl;
        else cout <<ans+1<<endl;
    }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Incorrect 3 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Incorrect 3 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Incorrect 3 ms 9820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 23096 KB Output is correct
2 Correct 319 ms 22892 KB Output is correct
3 Correct 281 ms 23004 KB Output is correct
4 Correct 240 ms 23480 KB Output is correct
5 Correct 251 ms 23224 KB Output is correct
6 Correct 269 ms 23224 KB Output is correct
7 Correct 258 ms 22968 KB Output is correct
8 Correct 265 ms 23188 KB Output is correct
9 Correct 125 ms 22456 KB Output is correct
10 Correct 245 ms 22716 KB Output is correct
11 Correct 316 ms 22456 KB Output is correct
12 Correct 272 ms 23224 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -