Submission #575843

#	Time	Username	Problem	Language	Result	Execution time	Memory
575843		MohamedAliSaidane	Event Hopping (BOI22_events)	C++14	0 / 100	475 ms	524288 KiB

events

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second

        ///#define int ll

        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

        const int nax = 1e5 + 4;
        int n, q, k = 1;
        set<pii> st[4 * nax];
        indexed_set nid;
        int tr[nax], tl[nax], d[nax], sp[nax][20];
        vpi v[2 * nax];
        vi ef;
        vi adj[nax], rev_adj[nax];

        void build(int p, int l, int r)
        {
            if(l == r)
            {
                for(auto e: v[l])
                    st[p].insert(e);
                return ;
            }
            build(2 * p, l, (l+r)/2);
            build(2 *p + 1, (l+r)/2 + 1,r);
            st[p] = st[2 * p];
            for(auto e: st[2 * p + 1])
                st[p].insert(e);
            return ;
        }
        void update(int i)
        {
            int idx = i + k;
            st[idx].erase({tl[i],i});
            idx /= 2;
            while(i)
            {
                st[idx].erase({tl[i],i});
                i /= 2;
            }
            return;
        }
        void upd(int p, int l, int r, int i, int j, int idx)
        {
            if( i > j)
                return ;
            if(l >= i && r <= j)
            {
                for(auto e: st[p])
                {
                    ef.pb(e.ss);
                }
                return ;
            }
            int m = (l+ r)/2;
            upd(2 * p,l,m,i,min(j,m),idx);
            upd(2*p+1,m+1,r,max(i,m+1),j,idx);
            return ;
        }
        void dfs(int x, int p = -1)
        {
            d[x] = p ==-1? 0: d[p] + 1;
            sp[x][0] = p== -1? x: p;
           // cout << x << ' ' << d[x] << '\n';
            for(auto e: adj[x])
            {
                dfs(e,x);
            }
        }
        int jump(int a, int k)
        {
            if(k < 0)
                return -1;
            for(int i = 0; i < 20; i ++)
                if((1 << i) & k)
                    a = sp[a][i];
            return a;
        }
        void solve()
        {
            cin >> n >> q;
            for(int i = 0; i < n; i ++)
            {
                cin >> tl[i] >> tr[i];
                nid.insert(tl[i]);
                nid.insert(tr[i]);
            }
            k = 1;
            while(k < (int)(nid.size()))
                k = (k << 1);
            for(int i = 0;i  < n; i ++)
            {
                tl[i] = nid.order_of_key(tl[i]);
                tr[i] = nid.order_of_key(tr[i]);
                v[tr[i]].pb({tl[i],i});
            }
            build(1,0,k - 1);
            bool vis[n]; memset(vis,false,sizeof(vis));
            for(int i=  0; i < n;i ++)
            {
                upd(1,0,k-1,tl[i], tr[i],i);
                for(auto u: ef)
                    if(u != i)
                        adj[i].pb(u);
                ef.clear();
            }
            for(int i = 0; i < n; i++)
            {
                for(auto e: adj[i])
                {
                        rev_adj[e].pb(i);
                        //cout << i << ' ' << e << '\n';
                }
            }
            for(int i = 0; i < n ;i ++)
            {
                if(rev_adj[i].size() == 0)
                    dfs(i);
            }
            for(int j = 1; j < 20; j++)
                for(int i=  0; i < n ;i ++)
                    sp[i][j] = sp[sp[i][j-1]][j-1];

            while(q--)
            {
                int s, e;
                cin >> s >> e;
                s--; e--;
                int c= jump(s,d[s] - d[e]);
                if(c == e)
                    cout << d[s] - d[e] << '\n';
                else if(tl[s] == tl[e] && tr[s] == tr[e])
                    cout << 1 << '\n';
                else
                    cout << "impossible\n";
            }
        }

        int32_t main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            int tt = 1;
            while(tt --)
                solve();
        }

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