oj.uz

Submission #986829

# Submission time Handle Problem Language Result Execution time Memory
986829 2024-05-21T10:07:31 Z alexdd Event Hopping (BOI22_events) C++17
20 / 100
 250 ms 47704 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(e[x].first).second;
    }
    //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);
            }
        }
        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 3 ms 10332 KB Output is correct
2 Correct 177 ms 34092 KB Output is correct
3 Correct 192 ms 34092 KB Output is correct
4 Correct 206 ms 34156 KB Output is correct
5 Incorrect 196 ms 36356 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10308 KB Output is correct
2 Correct 3 ms 10328 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Incorrect 4 ms 10392 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 10308 KB Output is correct
2 Correct 3 ms 10328 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Incorrect 4 ms 10392 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 10308 KB Output is correct
2 Correct 3 ms 10328 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Incorrect 4 ms 10392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 34096 KB Output is correct
2 Correct 182 ms 34184 KB Output is correct
3 Correct 184 ms 34092 KB Output is correct
4 Correct 232 ms 45672 KB Output is correct
5 Correct 184 ms 37784 KB Output is correct
6 Correct 236 ms 47696 KB Output is correct
7 Correct 240 ms 47588 KB Output is correct
8 Correct 234 ms 47704 KB Output is correct
9 Correct 217 ms 44880 KB Output is correct
10 Correct 250 ms 47356 KB Output is correct
11 Correct 228 ms 46932 KB Output is correct
12 Correct 249 ms 47184 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 177 ms 34092 KB Output is correct
3 Correct 192 ms 34092 KB Output is correct
4 Correct 206 ms 34156 KB Output is correct
5 Incorrect 196 ms 36356 KB Output isn't correct
6 Halted 0 ms 0 KB -