oj.uz

Submission #660095

# Submission time Handle Problem Language Result Execution time Memory
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

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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