oj.uz

Submission #986844

# Submission time Handle Problem Language Result Execution time Memory
986844 2024-05-21T10:36:30 Z alexdd Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 26632 KB 
#include<iostream>
#include<map>
#include<vector>
using namespace std;
pair<int,int> aib[200005];
pair<int,int> qry(int poz)
{
    pair<int,int> aux={0,0};
    for(int i=poz;i<=200002;i+=(i&(-i)))
        aux = max(aux, aib[i]);
    return aux;
}
void upd(int poz, pair<int,int> newv)
{
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[i] = max(aib[i], newv);
}

int n,q,cate;
map<int,int> mp,nrm;
pair<int,int> e[100005];
vector<int> caple[200005],capri[200005];
int nxt[100005][17];
void calc_nxt()
{
    for(int i=1;i<=n;i++)
    {
        caple[e[i].first].push_back(i);
        capri[e[i].second].push_back(i);
    }
    /*for(int i=1;i<=cate;i++)
    {
        for(auto x:caple[i])
            upd(e[x].first,{e[x].second,x});
        for(auto x:capri[i])
            nxt[x][0] = qry(1).second;
    }*/
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(e[j].first <= e[i].second && e[i].second <= e[j].second)
            {
                if(nxt[i][0]==0 || e[j].second > e[nxt[i][0]].second)
                    nxt[i][0]=j;
            }
        }
    }
    //for(int i=1;i<=n;i++) cout<<i<<" "<<nxt[i][0]<<" nxt\n";
    for(int p=1;p<17;p++)
        for(int i=1;i<=n;i++)
            nxt[i][p] = nxt[nxt[i][p-1]][p-1];
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    int le,ri;
    for(int i=1;i<=n;i++)
    {
        cin>>le>>ri;
        e[i]={le,ri};
        mp[le]++;
        mp[ri]++;
    }
    for(auto it:mp) nrm[it.first]=++cate;
    for(int i=1;i<=n;i++) e[i] = {nrm[e[i].first],nrm[e[i].second]};
    calc_nxt();
    while(q--)
    {
        cin>>le>>ri;
        if(le==ri)
        {
            cout<<0<<"\n";
            continue;
        }
        if(e[ri].second < e[le].second)
        {
            cout<<"impossible\n";
            continue;
        }
        if(e[ri].first <= e[le].second)
        {
            cout<<1<<"\n";
            continue;
        }
        int cnt=2;
        for(int i=16;i>=0;i--)
        {
            if(e[nxt[le][i]].second < e[ri].first)
            {
                le = nxt[le][i];
                cnt += (1<<i);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(e[i].first<=e[le].second && e[le].second<=e[i].second && e[ri].first <= e[i].second && e[i].second <= e[ri].second)
            {
                le=i;
                break;
            }
        }
        if(e[ri].first <= e[le].second && e[le].second <= e[ri].second)
            cout<<cnt<<"\n";
        else
            cout<<"impossible\n";
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Execution timed out 1540 ms 26632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 8 ms 10076 KB Output is correct
4 Correct 7 ms 10076 KB Output is correct
5 Incorrect 8 ms 10072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 8 ms 10076 KB Output is correct
4 Correct 7 ms 10076 KB Output is correct
5 Incorrect 8 ms 10072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 8 ms 10076 KB Output is correct
4 Correct 7 ms 10076 KB Output is correct
5 Incorrect 8 ms 10072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1545 ms 26452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Execution timed out 1540 ms 26632 KB Time limit exceeded
3 Halted 0 ms 0 KB -