oj.uz

답안 #993115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993115 2024-06-05T10:22:13 Z MarwenElarbi Event Hopping (BOI22_events) C++17
20 / 100
 271 ms 24308 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,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[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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 240 ms 22992 KB Output is correct
3 Correct 247 ms 22848 KB Output is correct
4 Correct 271 ms 23228 KB Output is correct
5 Incorrect 247 ms 23004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Incorrect 3 ms 9816 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Incorrect 3 ms 9816 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Incorrect 3 ms 9816 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 22968 KB Output is correct
2 Correct 254 ms 23684 KB Output is correct
3 Correct 268 ms 23224 KB Output is correct
4 Correct 230 ms 24308 KB Output is correct
5 Correct 245 ms 23224 KB Output is correct
6 Correct 249 ms 23224 KB Output is correct
7 Correct 253 ms 23064 KB Output is correct
8 Correct 256 ms 23228 KB Output is correct
9 Correct 103 ms 22344 KB Output is correct
10 Correct 254 ms 22832 KB Output is correct
11 Correct 243 ms 22460 KB Output is correct
12 Correct 253 ms 22712 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 240 ms 22992 KB Output is correct
3 Correct 247 ms 22848 KB Output is correct
4 Correct 271 ms 23228 KB Output is correct
5 Incorrect 247 ms 23004 KB Output isn't correct
6 Halted 0 ms 0 KB -