oj.uz

답안 #993445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993445 2024-06-05T16:39:50 Z MarwenElarbi Event Hopping (BOI22_events) C++17
20 / 100
 301 ms 23324 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;
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 264 ms 23004 KB Output is correct
3 Correct 257 ms 23228 KB Output is correct
4 Correct 273 ms 22916 KB Output is correct
5 Correct 265 ms 22920 KB Output is correct
6 Correct 301 ms 22968 KB Output is correct
7 Incorrect 253 ms 22972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 588 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 540 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 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 588 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 540 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 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 588 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 540 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 22884 KB Output is correct
2 Correct 256 ms 22968 KB Output is correct
3 Correct 260 ms 22968 KB Output is correct
4 Correct 240 ms 23324 KB Output is correct
5 Correct 256 ms 23224 KB Output is correct
6 Correct 263 ms 22976 KB Output is correct
7 Correct 263 ms 22968 KB Output is correct
8 Correct 264 ms 23232 KB Output is correct
9 Correct 121 ms 21176 KB Output is correct
10 Correct 260 ms 22712 KB Output is correct
11 Correct 249 ms 22456 KB Output is correct
12 Correct 257 ms 22712 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 264 ms 23004 KB Output is correct
3 Correct 257 ms 23228 KB Output is correct
4 Correct 273 ms 22916 KB Output is correct
5 Correct 265 ms 22920 KB Output is correct
6 Correct 301 ms 22968 KB Output is correct
7 Incorrect 253 ms 22972 KB Output isn't correct
8 Halted 0 ms 0 KB -