oj.uz

Submission #595597

# Submission time Handle Problem Language Result Execution time Memory
595597 2022-07-13T21:01:22 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 27300 KB 
#include <bits/stdc++.h>
#define MAX 5005
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*2,&x.first});
            comprime.push_back({x.second*2 + (1),&x.second});
        }
        std::sort(comprime.begin(),comprime.end());
        int last=-1,cord=1;
        for(auto&x:comprime){
            if(x.first&1){
                if(last==x.first-1){
                    *x.second=cord;
                }else *x.second=cord+1;
            }
            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 596 KB Output is correct
2 Runtime error 42 ms 5556 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 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 341 ms 8732 KB Output is correct
4 Correct 331 ms 8648 KB Output is correct
5 Correct 324 ms 8596 KB Output is correct
6 Correct 253 ms 8548 KB Output is correct
7 Correct 406 ms 8672 KB Output is correct
8 Correct 377 ms 8632 KB Output is correct
9 Correct 104 ms 8492 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 341 ms 8732 KB Output is correct
4 Correct 331 ms 8648 KB Output is correct
5 Correct 324 ms 8596 KB Output is correct
6 Correct 253 ms 8548 KB Output is correct
7 Correct 406 ms 8672 KB Output is correct
8 Correct 377 ms 8632 KB Output is correct
9 Correct 104 ms 8492 KB Output is correct
10 Correct 0 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 353 ms 8588 KB Output is correct
13 Correct 331 ms 8580 KB Output is correct
14 Correct 333 ms 8540 KB Output is correct
15 Correct 252 ms 8524 KB Output is correct
16 Correct 429 ms 8764 KB Output is correct
17 Correct 379 ms 8560 KB Output is correct
18 Correct 108 ms 8596 KB Output is correct
19 Execution timed out 1586 ms 27300 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 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 341 ms 8732 KB Output is correct
4 Correct 331 ms 8648 KB Output is correct
5 Correct 324 ms 8596 KB Output is correct
6 Correct 253 ms 8548 KB Output is correct
7 Correct 406 ms 8672 KB Output is correct
8 Correct 377 ms 8632 KB Output is correct
9 Correct 104 ms 8492 KB Output is correct
10 Correct 0 ms 596 KB Output is correct
11 Correct 0 ms 596 KB Output is correct
12 Correct 333 ms 8576 KB Output is correct
13 Correct 334 ms 8668 KB Output is correct
14 Correct 321 ms 8652 KB Output is correct
15 Correct 261 ms 8652 KB Output is correct
16 Correct 400 ms 8588 KB Output is correct
17 Correct 377 ms 8780 KB Output is correct
18 Correct 99 ms 8512 KB Output is correct
19 Runtime error 40 ms 5604 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 42 ms 5512 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 596 KB Output is correct
2 Runtime error 42 ms 5556 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -