oj.uz

Submission #986841

# Submission time Handle Problem Language Result Execution time Memory
986841 2024-05-21T10:25:13 Z alexdd Event Hopping (BOI22_events) C++17
30 / 100
 264 ms 47956 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++) 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 169 ms 35924 KB Output is correct
3 Correct 167 ms 35924 KB Output is correct
4 Correct 177 ms 35920 KB Output is correct
5 Correct 179 ms 37360 KB Output is correct
6 Correct 187 ms 39364 KB Output is correct
7 Correct 216 ms 39800 KB Output is correct
8 Correct 206 ms 47956 KB Output is correct
9 Correct 218 ms 47844 KB Output is correct
10 Correct 186 ms 37696 KB Output is correct
11 Correct 202 ms 41808 KB Output is correct
12 Correct 101 ms 33928 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9948 KB Output is correct
4 Correct 5 ms 9880 KB Output is correct
5 Incorrect 5 ms 9876 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 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9948 KB Output is correct
4 Correct 5 ms 9880 KB Output is correct
5 Incorrect 5 ms 9876 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 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9948 KB Output is correct
4 Correct 5 ms 9880 KB Output is correct
5 Incorrect 5 ms 9876 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 174 ms 35988 KB Output is correct
2 Correct 189 ms 36300 KB Output is correct
3 Correct 197 ms 35992 KB Output is correct
4 Correct 222 ms 46800 KB Output is correct
5 Correct 178 ms 36404 KB Output is correct
6 Correct 236 ms 46356 KB Output is correct
7 Correct 264 ms 46328 KB Output is correct
8 Correct 229 ms 46416 KB Output is correct
9 Correct 236 ms 44368 KB Output is correct
10 Correct 244 ms 45952 KB Output is correct
11 Correct 247 ms 45464 KB Output is correct
12 Correct 242 ms 45928 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 169 ms 35924 KB Output is correct
3 Correct 167 ms 35924 KB Output is correct
4 Correct 177 ms 35920 KB Output is correct
5 Correct 179 ms 37360 KB Output is correct
6 Correct 187 ms 39364 KB Output is correct
7 Correct 216 ms 39800 KB Output is correct
8 Correct 206 ms 47956 KB Output is correct
9 Correct 218 ms 47844 KB Output is correct
10 Correct 186 ms 37696 KB Output is correct
11 Correct 202 ms 41808 KB Output is correct
12 Correct 101 ms 33928 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9948 KB Output is correct
16 Correct 5 ms 9880 KB Output is correct
17 Incorrect 5 ms 9876 KB Output isn't correct
18 Halted 0 ms 0 KB -