oj.uz

답안 #849856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849856 2023-09-15T13:14:53 Z Ahmed57 Event Hopping (BOI22_events) C++17
20 / 100
 429 ms 31348 KB 
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.first.second<b.first.second;
}
int P[100001][17],ind[100001];
signed main(){
    int n,q;cin>>n>>q;
    vector<pair<pair<int,int>,int>> v;
    map<int,int> comp,sav;
    for(int i = 0;i<n;i++){
        int a,b;
        cin>>a>>b;
        comp[a]++;comp[b]++;
        v.push_back({{a,b},i});
    }
    long long z = 0;
    for(auto i:comp){
        sav[i.first] = ++z;
    }
    for(int i = 0;i<n;i++){
        v[i].first.first = sav[v[i].first.first];
        v[i].first.second = sav[v[i].first.second];
    }
    sort(v.begin(),v.end(),cmp);
    int in = 0;
    for(int i = 0;i<v.size();i++){
        ind[v[i].second] = i;
        while(in<n&&v[in].first.first<=v[i].first.second){
            in++;
        }
        P[i][0] = in-1;
    }
    for(int i = n-1;i>=0;i--){
        for(int j = 1;j<17;j++){
            P[i][j] = P[P[i][j-1]][j-1];
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        a--;b--;
        if(ind[a]>ind[b]){
        cout<<"impossible\n";
        continue;
        }else if(ind[a]==ind[b]){
        cout<<0<<endl;
        continue;
        }
        int sum = 0 , cur = ind[a];
        for(int i = 16;i>=0;i--){
            if(v[P[cur][i]].first.second<v[ind[b]].first.second){
                sum+=(1<<i);
                cur = P[cur][i];
            }
        }
        if(v[P[cur][0]].first.second>=v[ind[b]].first.second){
            cout<<sum+1<<endl;
        }else cout<<"impossible\n";
    }
}

Compilation message

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 18448 KB Output is correct
2 Correct 317 ms 18688 KB Output is correct
3 Correct 330 ms 18464 KB Output is correct
4 Correct 360 ms 28308 KB Output is correct
5 Correct 323 ms 18912 KB Output is correct
6 Correct 416 ms 28480 KB Output is correct
7 Correct 383 ms 31072 KB Output is correct
8 Correct 401 ms 31348 KB Output is correct
9 Correct 214 ms 29240 KB Output is correct
10 Correct 391 ms 30828 KB Output is correct
11 Correct 429 ms 30580 KB Output is correct
12 Correct 409 ms 30708 KB Output is correct

Subtask #6
0 / 30.0

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