oj.uz

Submission #864181

# Submission time Handle Problem Language Result Execution time Memory
864181 2023-10-22T08:09:07 Z vnm06 Event Hopping (BOI22_events) C++14
20 / 100
 91 ms 12884 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

int n, q;
int doseg[100005];
int tree[400005];

void update(int v, int le, int ri, int pos)
{
    if(le==ri) tree[v]=pos;
    else
    {
        int mid=(le+ri)/2;
        if(pos<=mid) update(2*v, le, mid, pos);
        else update(2*v+1, mid+1, ri, pos);
        if(doseg[tree[2*v]]<doseg[tree[2*v+1]]) tree[v]=tree[2*v];
        else tree[v]=tree[2*v+1];
    }
}

int query(int v, int le, int ri, int be, int en)
{
    if(le>en || ri<be) return n;
    else if(be<=le && ri<=en) return tree[v];
    else
    {
        int mid=(le+ri)/2;
        int p1=query(2*v, le, mid, be, en), p2=query(2*v+1, mid+1, ri, be, en);
        if(doseg[p1]<doseg[p2]) return p1;
        else return p2;
    }
}

struct event
{
    int be, en, nom;
    event() {}
    event(int a, int b, int c)
    {
        be=a;
        en=b;
        nom=c;
    }
};

bool operator<(event p, event q)
{
    return p.en<q.en;
}

int nnom[100005];
event ev[100005];
int par[20][100005];

void fill_table()
{
    for(int i=1; i<20; i++)
    {
        for(int j=0; j<n; j++) par[i][j]=par[i-1][par[i-1][j]];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=0; i<n; i++)
    {
        cin>>ev[i].be>>ev[i].en;
        ev[i].nom=i+1;
    }
    sort(ev, ev+n);
    for(int i=0; i<n; i++) nnom[ev[i].nom]=i;
    for(int i=0; i<400005; i++) tree[i]=n;
    doseg[n]=1e9;
    for(int i=0; i<n; i++)
    {
        int le=-1, ri=i;
        while(ri-le>1)
        {
            int mid=(le+ri)/2;
            if(ev[mid].en>=ev[i].be) ri=mid;
            else le=mid;
        }
        doseg[i]=ri;
        update(1, 0, n-1, i);
        par[0][i]=query(1, 0, n-1, doseg[i], i);
    }
    fill_table();
    for(int i=0; i<q; i++)
    {
        int le, ri;
        cin>>le>>ri;
        le=nnom[le];
        ri=nnom[ri];
        if(le==ri) cout<<0<<endl;
        else if(ev[le].en==ev[ri].en) cout<<1<<endl;
        else if(le>ri) cout<<"impossible\n";
        else if(doseg[par[19][ri]]>le) cout<<"impossible\n";
        else if(doseg[ri]<=le) cout<<1<<endl;
        else
        {
            int brpr=0;
            for(int i=19; i>=0; i--)
            {
                int p2=par[i][ri];
                if(doseg[p2]>le)
                {
                    brpr+=(1<<i);
                    ri=p2;
                }
            }
            cout<<brpr+2<<endl;
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 76 ms 12348 KB Output is correct
3 Correct 75 ms 12368 KB Output is correct
4 Correct 85 ms 12372 KB Output is correct
5 Correct 76 ms 12284 KB Output is correct
6 Correct 85 ms 12368 KB Output is correct
7 Correct 76 ms 12368 KB Output is correct
8 Incorrect 68 ms 12736 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11244 KB Output is correct
6 Incorrect 3 ms 11100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11244 KB Output is correct
6 Incorrect 3 ms 11100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Correct 1 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 2 ms 11244 KB Output is correct
6 Incorrect 3 ms 11100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12368 KB Output is correct
2 Correct 82 ms 12388 KB Output is correct
3 Correct 83 ms 12240 KB Output is correct
4 Correct 68 ms 12884 KB Output is correct
5 Correct 88 ms 12628 KB Output is correct
6 Correct 88 ms 12628 KB Output is correct
7 Correct 91 ms 12404 KB Output is correct
8 Correct 82 ms 12624 KB Output is correct
9 Correct 52 ms 11600 KB Output is correct
10 Correct 80 ms 12096 KB Output is correct
11 Correct 82 ms 11812 KB Output is correct
12 Correct 80 ms 12116 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 76 ms 12348 KB Output is correct
3 Correct 75 ms 12368 KB Output is correct
4 Correct 85 ms 12372 KB Output is correct
5 Correct 76 ms 12284 KB Output is correct
6 Correct 85 ms 12368 KB Output is correct
7 Correct 76 ms 12368 KB Output is correct
8 Incorrect 68 ms 12736 KB Output isn't correct
9 Halted 0 ms 0 KB -