oj.uz

Submission #595593

# Submission time Handle Problem Language Result Execution time Memory
595593 2022-07-13T20:52:21 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 22348 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]);
}

void zerar(void){for(auto&x:tab)x=1e9;}

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,eventos[x].second);
            update(eventos[x].second,d+1);
            custos[x]=d;
            minimo=std::min(minimo,d+1);
        }
        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 1 ms 852 KB Output is correct
2 Runtime error 49 ms 5800 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 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 247 ms 8792 KB Output is correct
4 Correct 303 ms 8768 KB Output is correct
5 Correct 232 ms 8760 KB Output is correct
6 Correct 327 ms 8848 KB Output is correct
7 Correct 331 ms 8832 KB Output is correct
8 Correct 337 ms 8872 KB Output is correct
9 Correct 175 ms 8780 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 247 ms 8792 KB Output is correct
4 Correct 303 ms 8768 KB Output is correct
5 Correct 232 ms 8760 KB Output is correct
6 Correct 327 ms 8848 KB Output is correct
7 Correct 331 ms 8832 KB Output is correct
8 Correct 337 ms 8872 KB Output is correct
9 Correct 175 ms 8780 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 237 ms 8868 KB Output is correct
13 Correct 254 ms 8816 KB Output is correct
14 Correct 229 ms 8820 KB Output is correct
15 Correct 258 ms 8836 KB Output is correct
16 Correct 356 ms 8772 KB Output is correct
17 Correct 300 ms 8800 KB Output is correct
18 Correct 178 ms 8788 KB Output is correct
19 Execution timed out 1584 ms 22348 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 247 ms 8792 KB Output is correct
4 Correct 303 ms 8768 KB Output is correct
5 Correct 232 ms 8760 KB Output is correct
6 Correct 327 ms 8848 KB Output is correct
7 Correct 331 ms 8832 KB Output is correct
8 Correct 337 ms 8872 KB Output is correct
9 Correct 175 ms 8780 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 274 ms 8808 KB Output is correct
13 Correct 238 ms 8972 KB Output is correct
14 Correct 236 ms 8752 KB Output is correct
15 Correct 283 ms 8812 KB Output is correct
16 Correct 327 ms 8856 KB Output is correct
17 Correct 328 ms 9008 KB Output is correct
18 Correct 200 ms 8800 KB Output is correct
19 Runtime error 41 ms 5700 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 43 ms 5708 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 1 ms 852 KB Output is correct
2 Runtime error 49 ms 5800 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -