oj.uz

답안 #660095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660095 2022-11-20T10:59:23 Z Karuk Event Hopping (BOI22_events) C++14
20 / 100
 192 ms 29624 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
pair<int,int>max(pair<int,int>a,pair<int,int>b) {
    return a>b?a:b;
}
const int k=(1<<30);
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,q;cin>>n>>q;
    pair<int,int>a[n];
    pair<int,int> prev[n][25];
    vector<pair<pair<int,int>,int>>v;
    for(int i=0;i<n;i++) {
        int x,y;
        cin>>x>>y;
        a[i]={x,y};
        v.push_back({{x,1},i});
        v.push_back({{y,2},i});
    }
    sort(v.begin(),v.end());
    set<pair<int,int>>smalleststart;
    for(auto i:v) {
        if(i.first.second==2) {
            smalleststart.erase({a[i.second].first,i.second});
        } else {
                smalleststart.insert({i.first.first,i.second});
                prev[i.second][0]=(*smalleststart.begin());
        }
    }
    ///coord1,isbeginning,index
    for(int j=1;j<25;j++) {
        for(int i=0;i<n;i++) {
            prev[i][j]=prev[prev[i][j-1].second][j-1];
        }
    }
    for(int i=0;i<q;i++) {
        int x,y;cin>>x>>y;x--;y--;
        if(x==y)cout<<0<<endl;
        else if(a[x].second>=a[y].first && a[x].second<=a[y].second)cout<<1<<endl;
        else if(a[x].second>a[y].second){cout<<"impossible"<<endl;}
        else {
            int cnt=0;
            int cur=y;
            int en=a[x].second;
            for(int j=24;j>=0;j--) {
                if(prev[cur][j].first>en) {
                    cur=prev[cur][j].second;
                    cnt+=(1<<j);
                }
            }
            if(prev[cur][0].first>en)cout<<"impossible"<<endl;
            else cout<<cnt+2<<endl;
        }
    }
    return 0;
}
///9:30

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 23892 KB Output is correct
2 Correct 119 ms 23880 KB Output is correct
3 Correct 192 ms 23836 KB Output is correct
4 Correct 107 ms 27316 KB Output is correct
5 Correct 168 ms 27136 KB Output is correct
6 Correct 141 ms 27060 KB Output is correct
7 Correct 135 ms 26852 KB Output is correct
8 Correct 124 ms 27100 KB Output is correct
9 Correct 101 ms 29624 KB Output is correct
10 Correct 123 ms 26572 KB Output is correct
11 Correct 140 ms 27424 KB Output is correct
12 Correct 134 ms 26576 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -