oj.uz

Submission #660096

# Submission time Handle Problem Language Result Execution time Memory
660096 2022-11-20T11:01:13 Z Karuk Event Hopping (BOI22_events) C++14
20 / 100
 181 ms 27668 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(prev[x][24].first!=prev[y][24].first ||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);
                }
            }
            cout<<cnt+2<<endl;
        }
    }
    return 0;
}
///9:30

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 125 ms 23880 KB Output is correct
2 Correct 117 ms 23940 KB Output is correct
3 Correct 181 ms 23904 KB Output is correct
4 Correct 119 ms 24168 KB Output is correct
5 Correct 126 ms 24032 KB Output is correct
6 Correct 134 ms 23872 KB Output is correct
7 Correct 130 ms 23856 KB Output is correct
8 Correct 123 ms 24120 KB Output is correct
9 Correct 91 ms 27668 KB Output is correct
10 Correct 115 ms 23868 KB Output is correct
11 Correct 117 ms 24316 KB Output is correct
12 Correct 123 ms 23896 KB Output is correct

Subtask #6
0 / 30.0

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