Submission #667050

#	Time	Username	Problem	Language	Result	Execution time	Memory
667050		berr	Event Hopping (BOI22_events)	C++17	0 / 100	229 ms	22880 KiB

events

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+37;
vector<int> adj[N];
int d[N], p[N], vis[N], c[N];
array<int, 2> st[N*4];
map<int, int> mp;
// 1. subtask


void update(int v, int l, int r, int pos, array<int, 2> val)
{
    if(l==r&&l==pos) st[v]=max(st[v], val);
    else if(l>r) return;
    else
    {
        int mid=(l+r)/2;
        if(pos<=mid) update(v*2, l, mid, pos, val);
        else update(v*2+1, mid+1, r, pos, val);
        st[v]=max(st[v*2+1], st[v*2]);
    }
}

array<int, 2> get(int v, int l, int r, int tl, int tr)
{
    if(r<l) return {0, 0};
    if(l>tr||r<tl) return {0, 0};
    if(l>=tl&&r<=tr) return st[v];
    if(l==r) return {0, 0};
    int mid=(l+r)/2;

    return max(get(v*2, l, mid, tl, tr), get(v*2+1, mid+1, r, tl, tr));  
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q; cin>>n>>q;

    vector<array<int, 3>> a(n);
    vector<int> x;
    for(int i=0; i<n; i++)
    {
        cin>>a[i][0]>>a[i][1];
        a[i][2]=i; p[i]=i;
        x.push_back(a[i][0]);
        x.push_back(a[i][1]);
    }

    sort(x.begin(), x.end());
    int cnt=1;

    for(auto i: x)
    {
        if(mp.count(i)==0) mp[i]=cnt, cnt++;
    }


    for(int i=0; i<n; i++)
    {
        a[i][0]=mp[a[i][0]];
        a[i][1]=mp[a[i][1]];

    }

    sort(a.begin(), a.end());

    for(int i=n-1; i>=0; i--)
    {
        auto v=get(1, 0, n*2, a[i][0], a[i][1]);


        if(v[0]>=a[i][1])
        {
           adj[a[i][2]].push_back(v[1]);
           c[v[1]]++;
        }
        update(1, 0, n*2, a[i][0], {a[i][1], a[i][2]});

    }

    queue<array<int, 3>> qu; 

    for(int i=0; i<n; i++)
    {
        if(c[i]==0)
        {
            qu.push({i, 0, i});
        }
    }

    while(qu.size())
    {
        int v=qu.front()[0], u=qu.front()[1], par=qu.front()[2];
        qu.pop();
        d[v]=u; p[v]=par;

        if(adj[v].size()) qu.push({adj[v][0], u+1, par});
    }

    while(q--)
    {
        int s, e; cin>>s>>e;
        s--; e--;
        if(p[s]!=p[e]||d[e]<d[s]) cout<<"impossible"<<"\n";
        else cout<<d[e]-d[s]<<"\n";
    }


}

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