oj.uz

Submission #667050

# Submission time Handle Problem Language Result Execution time Memory
667050 2022-11-30T09:06:39 Z berr Event Hopping (BOI22_events) C++17
0 / 100
 229 ms 22880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 173 ms 16308 KB Output is correct
3 Correct 175 ms 16256 KB Output is correct
4 Correct 175 ms 16196 KB Output is correct
5 Incorrect 184 ms 17248 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 16336 KB Output is correct
2 Correct 173 ms 16272 KB Output is correct
3 Correct 187 ms 16256 KB Output is correct
4 Correct 191 ms 20648 KB Output is correct
5 Correct 188 ms 16628 KB Output is correct
6 Incorrect 229 ms 22880 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 173 ms 16308 KB Output is correct
3 Correct 175 ms 16256 KB Output is correct
4 Correct 175 ms 16196 KB Output is correct
5 Incorrect 184 ms 17248 KB Output isn't correct
6 Halted 0 ms 0 KB -