Submission #1094367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094367		ivaziva	Event Hopping (BOI22_events)	C++14	0 / 100	266 ms	18884 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100001
#define MAXM 20

int n,q;
int l[MAXN],r[MAXN];
vector<int> kompresija;
vector<pair<pair<int,int>,int>> queries;
pair<int,int> seg[MAXN*8];
int parent[MAXM][MAXN];

pair<int,int> mergee(pair<int,int> x,pair<int,int> y)
{
    if (x.first>y.first) return x;
    return y;
}

void update(int node,int l,int r,int pos,pair<int,int> val)
{
    if (l==r) seg[node]=val;
    else
    {
        int mid=(l+r)/2;
        if (pos<=mid) update(2*node,l,mid,pos,val);
        else update(2*node+1,mid+1,r,pos,val);
        seg[node]=mergee(seg[2*node],seg[2*node+1]);
    }
}

pair<int,int> query(int node,int l,int r,int a,int b)
{
    if (a>b) return {0,0};
    if (l==a and r==b) return seg[node];
    int mid=(l+r)/2;
    return mergee(query(2*node,l,mid,a,min(b,mid)),query(2*node+1,mid+1,r,max(a,mid+1),b));
}

int main()
{
    cin>>n>>q;
    for (int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        kompresija.push_back(l[i]);
        kompresija.push_back(r[i]);
    }
    sort(kompresija.begin(),kompresija.end());
    kompresija.erase(unique(kompresija.begin(),kompresija.end()),kompresija.end());
    for (int i=1;i<=n;i++)
    {
        l[i]=lower_bound(kompresija.begin(),kompresija.end(),l[i])-kompresija.begin();
        r[i]=lower_bound(kompresija.begin(),kompresija.end(),r[i])-kompresija.begin();
    }
    for (int i=1;i<=n;i++) queries.push_back({{l[i],r[i]},i});
    sort(queries.begin(),queries.end());
    for (int i=0;i<n;i++) update(1,0,2*MAXN-1,queries[i].first.first,{queries[i].first.second,queries[i].second});
    for (int i=0;i<n;i++)
    {
        pair<int,int> sol=query(1,0,2*MAXN-1,0,queries[i].first.second);
        if (sol.second==queries[i].second) continue;
        if (sol.first==0 and sol.second==0) continue;
        if (sol.first>=queries[i].first.second) parent[0][queries[i].second]=sol.second;
    }
    for (int j=1;j<MAXM;j++)
    {
        for (int i=1;i<=n;i++) parent[j][i]=parent[j-1][parent[j-1][i]];
    }
    for (int i=1;i<=q;i++)
    {
        int node1,node2;cin>>node1>>node2;
        if (node1==node2) {cout<<0<<endl;continue;}
        if (!(r[node1]<=r[node2])) {cout<<"Impossible"<<endl;continue;}
        if (l[node2]<=r[node1]) {cout<<1<<endl;continue;}
        int node=node1,ans=0;
        for (int j=MAXM-1;j>=0;j--)
        {
            if (parent[j][node]==0) continue;
            if (l[node2]>r[parent[j][node]] and r[parent[j][node]]<=r[node2]) {ans+=(1<<j);node=parent[j][node];}
        }
        node=parent[0][node];ans++;
        if (node==0) {cout<<"Impossible"<<endl;continue;}
        if (r[node]==r[node2]) cout<<ans<<endl;
        else if (l[node2]<=r[node] and r[node]<r[node2]) cout<<ans+1<<endl;
        else cout<<"Impossible"<<endl;
    }
}

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