oj.uz

Submission #595595

# Submission time Handle Problem Language Result Execution time Memory
595595 2022-07-13T20:55:06 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 19580 KB 
#include <bits/stdc++.h>
#define MAX 10005
int N,Q;
typedef std::pair<int,int> pii;
std::vector<pii> eventos;

std::vector<int> add[MAX];

std::vector<int> rem[MAX];

int tab[MAX*4];
int limpa[MAX*4];
int rodada=42;

void checa(int x){
    if(limpa[x]!=rodada){
        limpa[x]=rodada;
        tab[x]=1e9;
    }
}
int query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    checa(pos);
    if(la>r||ra<l)return 1e9;
    if(la>=l&&ra<=r){
        return tab[pos];
    }
    int m = (la+ra)/2;
    return std::min(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}

void update(int t,int k,int la=0,int ra=MAX-1,int pos=1){
    checa(pos);
    if(la>t||ra<t)return;
    if(la==ra){
        tab[pos]=std::min(tab[pos],k);
        return;
    }
    int m = (la+ra)/2;
    if(t<=m)
    update(t,k,la,m,pos*2);
    else
    update(t,k,m+1,ra,(pos*2)+1);
    checa(pos*2);
    checa((pos*2)+1);
    tab[pos]=std::min(tab[pos*2],tab[(pos*2)+1]);
}

typedef std::pair<int,int*> pipo;
int custos[101000];
int trava;
void simula(int x){
    ++rodada;
    update(eventos[x].second,1);
    for(int i=0;i!=trava+1;++i){
        int minimo=1e9;
        for(auto&x:rem[i]){
            int d = query(eventos[x].first,i);
            custos[x]=d;
            minimo=std::min(minimo,d+1);
        }
        update(i,minimo);
        for(auto&x:rem[i]){
            custos[x]=std::min(custos[x],minimo);
        }
    }
    custos[x]=0;
}
int tabp5[5005][5005];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>Q;
    for(int i=0;i!=N;++i){
        int a,b;
        std::cin>>a>>b;
        eventos.push_back({a,b});
    }

    {
        std::vector<pipo> comprime;
        for(auto&x:eventos){
            comprime.push_back({x.first,&x.first});
            comprime.push_back({x.second,&x.second});
        }
        std::sort(comprime.begin(),comprime.end());
        int last=-1,cord=1;
        for(auto&x:comprime){
            if(x.first!=last){
                last=x.first;
                ++cord;
            }
            *x.second=cord;
        }
        trava=cord;
    }
    for(int i=0;i!=N;++i){
        rem[eventos[i].second].push_back(i);
    }
    if(N<=5005){
        for(int i=0;i!=N;++i){
            simula(i);
            for(int j=0;j!=N;++j)
                tabp5[i][j]=custos[j];
        }
        for(int i=0;i!=Q;++i){
            int a,b;
            std::cin>>a>>b;
            --a;--b;
            int d = tabp5[a][b];
            if(d>1e6){
                std::cout<<"impossible\n";
            }else {
                std::cout<<d<<"\n";
            }
        }
        return 0;
    }
    for(int i=0;i!=Q;++i){
        int a,b;
        std::cin>>a>>b;
        --a;--b;
        simula(a);
        int d = custos[b];
        if(d>1e6){
            std::cout<<"impossible\n";
        }else {
            std::cout<<d<<"\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 852 KB Output is correct
2 Runtime error 42 ms 5788 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 231 ms 8804 KB Output is correct
4 Correct 236 ms 8844 KB Output is correct
5 Correct 230 ms 8792 KB Output is correct
6 Correct 282 ms 8860 KB Output is correct
7 Correct 419 ms 8864 KB Output is correct
8 Correct 411 ms 8852 KB Output is correct
9 Correct 116 ms 8724 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 231 ms 8804 KB Output is correct
4 Correct 236 ms 8844 KB Output is correct
5 Correct 230 ms 8792 KB Output is correct
6 Correct 282 ms 8860 KB Output is correct
7 Correct 419 ms 8864 KB Output is correct
8 Correct 411 ms 8852 KB Output is correct
9 Correct 116 ms 8724 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 228 ms 8836 KB Output is correct
13 Correct 236 ms 8780 KB Output is correct
14 Correct 226 ms 8768 KB Output is correct
15 Correct 288 ms 8784 KB Output is correct
16 Correct 442 ms 8844 KB Output is correct
17 Correct 427 ms 8788 KB Output is correct
18 Correct 113 ms 8776 KB Output is correct
19 Execution timed out 1589 ms 19580 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 231 ms 8804 KB Output is correct
4 Correct 236 ms 8844 KB Output is correct
5 Correct 230 ms 8792 KB Output is correct
6 Correct 282 ms 8860 KB Output is correct
7 Correct 419 ms 8864 KB Output is correct
8 Correct 411 ms 8852 KB Output is correct
9 Correct 116 ms 8724 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 257 ms 8784 KB Output is correct
13 Correct 261 ms 8992 KB Output is correct
14 Correct 268 ms 8872 KB Output is correct
15 Correct 288 ms 8796 KB Output is correct
16 Correct 475 ms 8800 KB Output is correct
17 Correct 429 ms 8900 KB Output is correct
18 Correct 140 ms 8804 KB Output is correct
19 Runtime error 53 ms 5772 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 5752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 852 KB Output is correct
2 Runtime error 42 ms 5788 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -