Submission #578436

#	Time	Username	Problem	Language	Result	Execution time	Memory
578436		abdzag	Event Hopping (BOI22_events)	C++17	100 / 100	633 ms	49236 KiB

events

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long inf=1e16;
struct Tree {
	typedef pair<int,int> T;
	static constexpr T unit = {INT_MAX,INT_MAX};
	T f(T a, T b) { return min(a, b); } // (any associative fn)
	vector<T> s; int n;
	Tree(int _n) {
        n=_n;
        s.assign(2*n,{INT_MAX,INT_MAX});
    }
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};
int main(){
    ll n,q;
    cin>>n>>q;
    map<ll,ll> mapping;
    Tree tree(2*n+10);
    vector<pair<ll,ll>> v(n);
    set<ll> coords;
    for(int i=0;i<n;i++)cin>>v[i].first>>v[i].second;
    for(int i=0;i<n;i++)coords.insert(v[i].first),coords.insert(v[i].second);
    ll l=0;
    for(auto a: coords)mapping[a]=l++;
    for(int i=0;i<n;i++){
        v[i].first=mapping[v[i].first];
        v[i].second=mapping[v[i].second];
        if(tree.query(v[i].second,v[i].second+1).first>v[i].first)tree.update(v[i].second,{v[i].first,i});
    }
    ll LOG=23;
    // Building the edges doesn't work properly.
    //Some intervals are getting self loops and I am not adding end points correcctly
    vector<vector<ll>> p(n,vector<ll>(LOG));
    for(int i=0;i<n;i++){
        pair<ll,ll> cur=tree.query(v[i].first,v[i].second+1);
        if(cur.first>=v[i].first){
            p[i][0]=i;
        }
        else p[i][0]=cur.second;
    }
    for(int j=1;j<LOG;j++){
        for(int i=0;i<n;i++)p[i][j]=p[p[i][j-1]][j-1];
    }
    for(int i=0;i<q;i++){
        ll s,f;
        cin>>s>>f;
        s--,f--;
        if(s==f){
            cout<<0<<endl;
            continue;
        }
        if(v[s].second>v[f].second){
            cout<<"impossible"<<endl;
            continue;
        }
        if(v[s].second>=v[f].first){
            cout<<1<<endl;
            continue;
        }
        ll ans=2,cur=f;
        for(int i=LOG-1;i>=0;i--){
            if(v[p[cur][i]].first>v[s].second){
                ans+=(1<<i);
                cur=p[cur][i];
            }
        }
        if(v[p[cur][0]].first<=v[s].second)cout<<ans<<endl;
        else cout<<"impossible"<<endl;
    }
    return 0;
}
/*
3 1
7 14
1 6
3 8
2 1
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30