oj.uz

Submission #986826

# Submission time Handle Problem Language Result Execution time Memory
986826 2024-05-21T10:05:45 Z alexdd Event Hopping (BOI22_events) C++17
0 / 100
 177 ms 53328 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[100005],capri[100005];
int nxt[100005][18];
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(e[x].first).second;
    }
    //for(int i=1;i<=n;i++) cout<<i<<" "<<nxt[i][0]<<" nxt\n";
    for(int p=1;p<18;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=0;
        for(int i=17;i>=0;i--)
        {
            if(e[nxt[le][i]].second < e[ri].first)
            {
                le = nxt[le][i];
                cnt += (1<<i);
            }
        }
        cnt+=2;
        le = nxt[le][0];
        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 2 ms 6492 KB Output is correct
2 Correct 164 ms 30004 KB Output is correct
3 Correct 158 ms 29756 KB Output is correct
4 Correct 177 ms 29804 KB Output is correct
5 Runtime error 112 ms 36016 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Incorrect 2 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Incorrect 2 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Incorrect 2 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 29788 KB Output is correct
2 Correct 158 ms 29776 KB Output is correct
3 Correct 167 ms 29768 KB Output is correct
4 Runtime error 150 ms 53328 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 164 ms 30004 KB Output is correct
3 Correct 158 ms 29756 KB Output is correct
4 Correct 177 ms 29804 KB Output is correct
5 Runtime error 112 ms 36016 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -