oj.uz

답안 #595612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
595612 2022-07-13T21:42:27 Z Deepesson Event Hopping (BOI22_events) C++17
40 / 100
 1284 ms 108888 KB 
#include <bits/stdc++.h>
#define MAX 200010
#define LSB(A) (A&(-A))
int N,Q;
typedef std::pair<int,int> pii;
std::vector<pii> eventos;

std::vector<int> add[MAX];

std::vector<int> rem[MAX];

int ft[MAX];

void upd(int a,int b){a+=3;
   // std::cout<<"Upd "<<a<<"\n";
    while(a<MAX){
        ft[a]=std::min(ft[a],b);
        a+=LSB(a);
    }
}

int query(int a){a+=3;
  //  std::cout<<"Upd "<<a<<"\n";
    int r=1e9;
    while(a>0){
        r=std::min(r,ft[a]);
        a-=LSB(a);
    }
    return r;
}

typedef std::pair<int,int*> pipo;
int custos[101000];
int trava;

int correntes[MAX],grupos[MAX];
int curgp=1;
int contr=1;
void simula(int x){
    int base = N*2 + 5;
    for(int i=0;i!=base;++i)ft[i]=1e9;
    upd(base-eventos[x].second-5,1);
    for(int i=0;i!=N;++i)custos[i]=1e9;
    for(int i=eventos[x].second;i!=trava+1;++i){
        int minimo=1e9;
        for(auto&x:rem[i]){
            int d = query(base-eventos[x].first-5);
            custos[x]=d;
          //  std::cout<<x<<" "<<d<<" "<<MAX-eventos[x].first-5<<" "<<MAX-i-5<<"!\n";
            minimo=std::min(minimo,d+1);
        }
        if(minimo==1e9){
            curgp++;
        }
        for(auto&x:rem[i]){
            grupos[x]=curgp;
            correntes[x]=contr;
            ++contr;
        }
      //  std::cout<<minimo<<"\n";
        upd(base-i-5,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,&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;
    }
    if(Q<=100){
        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";
            }
        }
        return 0;
    }else {///Caso 1
        simula(0);
        for(int i=0;i!=Q;++i){
            int a,b;
            std::cin>>a>>b;
            --a;--b;
            int d = correntes[b]-correntes[a];
            if(grupos[a]!=grupos[b]||d<0){
                std::cout<<"impossible\n";
            }else {
                std::cout<<d<<"\n";
            }
        }
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 74 ms 16772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 32 ms 17792 KB Output is correct
4 Correct 34 ms 17684 KB Output is correct
5 Correct 32 ms 17776 KB Output is correct
6 Correct 33 ms 17768 KB Output is correct
7 Correct 47 ms 17728 KB Output is correct
8 Correct 35 ms 17668 KB Output is correct
9 Correct 27 ms 17672 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 32 ms 17792 KB Output is correct
4 Correct 34 ms 17684 KB Output is correct
5 Correct 32 ms 17776 KB Output is correct
6 Correct 33 ms 17768 KB Output is correct
7 Correct 47 ms 17728 KB Output is correct
8 Correct 35 ms 17668 KB Output is correct
9 Correct 27 ms 17672 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 17740 KB Output is correct
13 Correct 34 ms 17740 KB Output is correct
14 Correct 33 ms 17684 KB Output is correct
15 Correct 32 ms 17696 KB Output is correct
16 Correct 51 ms 17684 KB Output is correct
17 Correct 34 ms 17740 KB Output is correct
18 Correct 26 ms 17680 KB Output is correct
19 Correct 708 ms 108500 KB Output is correct
20 Correct 708 ms 108464 KB Output is correct
21 Correct 706 ms 108700 KB Output is correct
22 Correct 701 ms 108888 KB Output is correct
23 Correct 951 ms 108880 KB Output is correct
24 Correct 779 ms 108600 KB Output is correct
25 Correct 1062 ms 108360 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 32 ms 17792 KB Output is correct
4 Correct 34 ms 17684 KB Output is correct
5 Correct 32 ms 17776 KB Output is correct
6 Correct 33 ms 17768 KB Output is correct
7 Correct 47 ms 17728 KB Output is correct
8 Correct 35 ms 17668 KB Output is correct
9 Correct 27 ms 17672 KB Output is correct
10 Correct 4 ms 9696 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 33 ms 17740 KB Output is correct
13 Correct 33 ms 17660 KB Output is correct
14 Correct 32 ms 17764 KB Output is correct
15 Correct 32 ms 17796 KB Output is correct
16 Correct 43 ms 17768 KB Output is correct
17 Correct 39 ms 17764 KB Output is correct
18 Correct 27 ms 17744 KB Output is correct
19 Correct 857 ms 15512 KB Output is correct
20 Correct 500 ms 15496 KB Output is correct
21 Correct 453 ms 14628 KB Output is correct
22 Correct 546 ms 15496 KB Output is correct
23 Correct 538 ms 15512 KB Output is correct
24 Correct 1284 ms 15612 KB Output is correct
25 Correct 215 ms 14672 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 16712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 74 ms 16772 KB Output isn't correct
3 Halted 0 ms 0 KB -