oj.uz

Submission #864175

# Submission time Handle Problem Language Result Execution time Memory
864175 2023-10-22T08:01:26 Z vnm06 Event Hopping (BOI22_events) C++14
20 / 100
 101 ms 12368 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;
    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 1 ms 10588 KB Output is correct
2 Correct 94 ms 11812 KB Output is correct
3 Correct 81 ms 11800 KB Output is correct
4 Correct 79 ms 12084 KB Output is correct
5 Correct 76 ms 11852 KB Output is correct
6 Correct 75 ms 11908 KB Output is correct
7 Correct 78 ms 11960 KB Output is correct
8 Incorrect 68 ms 12368 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 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Incorrect 3 ms 10740 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 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Incorrect 3 ms 10740 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 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Incorrect 3 ms 10740 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 76 ms 11856 KB Output is correct
2 Correct 76 ms 11636 KB Output is correct
3 Correct 82 ms 11724 KB Output is correct
4 Correct 69 ms 12196 KB Output is correct
5 Correct 86 ms 12316 KB Output is correct
6 Correct 89 ms 11860 KB Output is correct
7 Correct 88 ms 11912 KB Output is correct
8 Correct 101 ms 11940 KB Output is correct
9 Correct 54 ms 11092 KB Output is correct
10 Correct 80 ms 11468 KB Output is correct
11 Correct 81 ms 11348 KB Output is correct
12 Correct 80 ms 11472 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 94 ms 11812 KB Output is correct
3 Correct 81 ms 11800 KB Output is correct
4 Correct 79 ms 12084 KB Output is correct
5 Correct 76 ms 11852 KB Output is correct
6 Correct 75 ms 11908 KB Output is correct
7 Correct 78 ms 11960 KB Output is correct
8 Incorrect 68 ms 12368 KB Output isn't correct
9 Halted 0 ms 0 KB -