oj.uz

Submission #595611

# Submission time Handle Problem Language Result Execution time Memory
595611 2022-07-13T21:41:39 Z Deepesson Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 108752 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";
            }
        }
    }else {///Caso 1
        simula(0);
        for(int i=0;i!=Q;++i){
            int a,b;
            std::cin>>a>>b;
            --a;--b;
            simula(a);
            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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1581 ms 15504 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 9800 KB Output is correct
3 Correct 32 ms 17756 KB Output is correct
4 Correct 33 ms 17716 KB Output is correct
5 Correct 32 ms 17736 KB Output is correct
6 Correct 33 ms 17712 KB Output is correct
7 Correct 46 ms 17740 KB Output is correct
8 Correct 34 ms 17740 KB Output is correct
9 Correct 27 ms 17792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9800 KB Output is correct
3 Correct 32 ms 17756 KB Output is correct
4 Correct 33 ms 17716 KB Output is correct
5 Correct 32 ms 17736 KB Output is correct
6 Correct 33 ms 17712 KB Output is correct
7 Correct 46 ms 17740 KB Output is correct
8 Correct 34 ms 17740 KB Output is correct
9 Correct 27 ms 17792 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 32 ms 17756 KB Output is correct
13 Correct 31 ms 17788 KB Output is correct
14 Correct 33 ms 17796 KB Output is correct
15 Correct 33 ms 17756 KB Output is correct
16 Correct 42 ms 17680 KB Output is correct
17 Correct 36 ms 17688 KB Output is correct
18 Correct 28 ms 17748 KB Output is correct
19 Correct 703 ms 108492 KB Output is correct
20 Correct 722 ms 108460 KB Output is correct
21 Correct 711 ms 108752 KB Output is correct
22 Correct 690 ms 108740 KB Output is correct
23 Correct 983 ms 108688 KB Output is correct
24 Correct 780 ms 108732 KB Output is correct
25 Correct 1066 ms 108264 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9800 KB Output is correct
3 Correct 32 ms 17756 KB Output is correct
4 Correct 33 ms 17716 KB Output is correct
5 Correct 32 ms 17736 KB Output is correct
6 Correct 33 ms 17712 KB Output is correct
7 Correct 46 ms 17740 KB Output is correct
8 Correct 34 ms 17740 KB Output is correct
9 Correct 27 ms 17792 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9712 KB Output is correct
12 Correct 32 ms 17676 KB Output is correct
13 Correct 33 ms 17740 KB Output is correct
14 Correct 32 ms 17776 KB Output is correct
15 Correct 33 ms 17660 KB Output is correct
16 Correct 43 ms 17752 KB Output is correct
17 Correct 34 ms 17740 KB Output is correct
18 Correct 26 ms 17704 KB Output is correct
19 Correct 912 ms 15524 KB Output is correct
20 Correct 479 ms 15680 KB Output is correct
21 Correct 452 ms 14808 KB Output is correct
22 Correct 530 ms 15640 KB Output is correct
23 Correct 557 ms 15680 KB Output is correct
24 Correct 1195 ms 15688 KB Output is correct
25 Correct 210 ms 14860 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 15604 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 1581 ms 15504 KB Time limit exceeded
3 Halted 0 ms 0 KB -