oj.uz

답안 #595586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595586 2022-07-13T20:45:03 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 19324 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];
void simula(int x){
    ++rodada;
    update(eventos[x].second,1);
    for(int i=0;i!=MAX;++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;
        }
    }
    for(int i=0;i!=N;++i){
        add[eventos[i].first].push_back(i);
        rem[eventos[i].second].push_back(i);
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Execution timed out 1586 ms 19264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 9 ms 9812 KB Output is correct
3 Correct 90 ms 9812 KB Output is correct
4 Correct 93 ms 9916 KB Output is correct
5 Correct 86 ms 9812 KB Output is correct
6 Correct 89 ms 9812 KB Output is correct
7 Correct 101 ms 9940 KB Output is correct
8 Correct 99 ms 9940 KB Output is correct
9 Correct 78 ms 9812 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 9 ms 9812 KB Output is correct
3 Correct 90 ms 9812 KB Output is correct
4 Correct 93 ms 9916 KB Output is correct
5 Correct 86 ms 9812 KB Output is correct
6 Correct 89 ms 9812 KB Output is correct
7 Correct 101 ms 9940 KB Output is correct
8 Correct 99 ms 9940 KB Output is correct
9 Correct 78 ms 9812 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 87 ms 9908 KB Output is correct
13 Correct 95 ms 9908 KB Output is correct
14 Correct 89 ms 9920 KB Output is correct
15 Correct 85 ms 9812 KB Output is correct
16 Correct 92 ms 9920 KB Output is correct
17 Correct 97 ms 9924 KB Output is correct
18 Correct 84 ms 9864 KB Output is correct
19 Execution timed out 1592 ms 10236 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 9 ms 9812 KB Output is correct
3 Correct 90 ms 9812 KB Output is correct
4 Correct 93 ms 9916 KB Output is correct
5 Correct 86 ms 9812 KB Output is correct
6 Correct 89 ms 9812 KB Output is correct
7 Correct 101 ms 9940 KB Output is correct
8 Correct 99 ms 9940 KB Output is correct
9 Correct 78 ms 9812 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 8 ms 9812 KB Output is correct
12 Correct 87 ms 9812 KB Output is correct
13 Correct 87 ms 9812 KB Output is correct
14 Correct 84 ms 9812 KB Output is correct
15 Correct 95 ms 9908 KB Output is correct
16 Correct 102 ms 9924 KB Output is correct
17 Correct 94 ms 9940 KB Output is correct
18 Correct 78 ms 9868 KB Output is correct
19 Execution timed out 1564 ms 19324 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1553 ms 19200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Execution timed out 1586 ms 19264 KB Time limit exceeded
3 Halted 0 ms 0 KB -