oj.uz

Submission #595592

# Submission time Handle Problem Language Result Execution time Memory
595592 2022-07-13T20:51:47 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 27352 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 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 4 ms 9812 KB Output is correct
2 Execution timed out 1598 ms 16104 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 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 311 ms 17732 KB Output is correct
4 Correct 301 ms 17740 KB Output is correct
5 Correct 307 ms 17796 KB Output is correct
6 Correct 315 ms 17780 KB Output is correct
7 Correct 446 ms 17860 KB Output is correct
8 Correct 365 ms 17812 KB Output is correct
9 Correct 281 ms 17856 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 311 ms 17732 KB Output is correct
4 Correct 301 ms 17740 KB Output is correct
5 Correct 307 ms 17796 KB Output is correct
6 Correct 315 ms 17780 KB Output is correct
7 Correct 446 ms 17860 KB Output is correct
8 Correct 365 ms 17812 KB Output is correct
9 Correct 281 ms 17856 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 374 ms 17732 KB Output is correct
13 Correct 306 ms 17748 KB Output is correct
14 Correct 310 ms 17800 KB Output is correct
15 Correct 328 ms 17784 KB Output is correct
16 Correct 417 ms 17836 KB Output is correct
17 Correct 382 ms 17812 KB Output is correct
18 Correct 281 ms 17756 KB Output is correct
19 Execution timed out 1578 ms 27352 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 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 311 ms 17732 KB Output is correct
4 Correct 301 ms 17740 KB Output is correct
5 Correct 307 ms 17796 KB Output is correct
6 Correct 315 ms 17780 KB Output is correct
7 Correct 446 ms 17860 KB Output is correct
8 Correct 365 ms 17812 KB Output is correct
9 Correct 281 ms 17856 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 331 ms 17836 KB Output is correct
13 Correct 311 ms 17876 KB Output is correct
14 Correct 297 ms 17824 KB Output is correct
15 Correct 327 ms 17848 KB Output is correct
16 Correct 410 ms 17804 KB Output is correct
17 Correct 375 ms 17752 KB Output is correct
18 Correct 247 ms 17712 KB Output is correct
19 Execution timed out 1577 ms 16096 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 1592 ms 16168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9812 KB Output is correct
2 Execution timed out 1598 ms 16104 KB Time limit exceeded
3 Halted 0 ms 0 KB -