oj.uz

Submission #595589

# Submission time Handle Problem Language Result Execution time Memory
595589 2022-07-13T20:47:38 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 16124 KB 
#include <bits/stdc++.h>
#define MAX 200005
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 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!=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 5 ms 9684 KB Output is correct
2 Execution timed out 1593 ms 16028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 34 ms 9812 KB Output is correct
4 Correct 35 ms 9876 KB Output is correct
5 Correct 33 ms 9812 KB Output is correct
6 Correct 36 ms 9860 KB Output is correct
7 Correct 44 ms 9812 KB Output is correct
8 Correct 41 ms 9904 KB Output is correct
9 Correct 28 ms 9884 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 34 ms 9812 KB Output is correct
4 Correct 35 ms 9876 KB Output is correct
5 Correct 33 ms 9812 KB Output is correct
6 Correct 36 ms 9860 KB Output is correct
7 Correct 44 ms 9812 KB Output is correct
8 Correct 41 ms 9904 KB Output is correct
9 Correct 28 ms 9884 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 36 ms 9812 KB Output is correct
13 Correct 34 ms 9888 KB Output is correct
14 Correct 33 ms 9896 KB Output is correct
15 Correct 36 ms 9812 KB Output is correct
16 Correct 43 ms 9812 KB Output is correct
17 Correct 42 ms 9896 KB Output is correct
18 Correct 28 ms 9888 KB Output is correct
19 Execution timed out 1587 ms 10160 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 34 ms 9812 KB Output is correct
4 Correct 35 ms 9876 KB Output is correct
5 Correct 33 ms 9812 KB Output is correct
6 Correct 36 ms 9860 KB Output is correct
7 Correct 44 ms 9812 KB Output is correct
8 Correct 41 ms 9904 KB Output is correct
9 Correct 28 ms 9884 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 34 ms 9848 KB Output is correct
13 Correct 35 ms 9812 KB Output is correct
14 Correct 36 ms 9876 KB Output is correct
15 Correct 35 ms 9896 KB Output is correct
16 Correct 45 ms 9896 KB Output is correct
17 Correct 44 ms 9812 KB Output is correct
18 Correct 28 ms 9812 KB Output is correct
19 Execution timed out 1590 ms 16120 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 16124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1593 ms 16028 KB Time limit exceeded
3 Halted 0 ms 0 KB -