oj.uz

Submission #595606

# Submission time Handle Problem Language Result Execution time Memory
595606 2022-07-13T21:34:28 Z Deepesson Event Hopping (BOI22_events) C++17
25 / 100
 762 ms 100852 KB 
#include <bits/stdc++.h>
#define MAX 10010
#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;
void simula(int x){
    for(auto&x:ft)x=1e9;
    upd(MAX-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(MAX-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);
        }
      //  std::cout<<minimo<<"\n";
        upd(MAX-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;
    }
    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 852 KB Output is correct
2 Runtime error 44 ms 5836 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 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 25 ms 8816 KB Output is correct
4 Correct 26 ms 8824 KB Output is correct
5 Correct 25 ms 8840 KB Output is correct
6 Correct 25 ms 8736 KB Output is correct
7 Correct 30 ms 8816 KB Output is correct
8 Correct 26 ms 8828 KB Output is correct
9 Correct 23 ms 8864 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 25 ms 8816 KB Output is correct
4 Correct 26 ms 8824 KB Output is correct
5 Correct 25 ms 8840 KB Output is correct
6 Correct 25 ms 8736 KB Output is correct
7 Correct 30 ms 8816 KB Output is correct
8 Correct 26 ms 8828 KB Output is correct
9 Correct 23 ms 8864 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 32 ms 8836 KB Output is correct
13 Correct 25 ms 8824 KB Output is correct
14 Correct 24 ms 8788 KB Output is correct
15 Correct 23 ms 8788 KB Output is correct
16 Correct 30 ms 8788 KB Output is correct
17 Correct 27 ms 8816 KB Output is correct
18 Correct 24 ms 8764 KB Output is correct
19 Correct 527 ms 99524 KB Output is correct
20 Correct 531 ms 100468 KB Output is correct
21 Correct 530 ms 100656 KB Output is correct
22 Correct 543 ms 100852 KB Output is correct
23 Correct 762 ms 100568 KB Output is correct
24 Correct 577 ms 100740 KB Output is correct
25 Correct 761 ms 100208 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 25 ms 8816 KB Output is correct
4 Correct 26 ms 8824 KB Output is correct
5 Correct 25 ms 8840 KB Output is correct
6 Correct 25 ms 8736 KB Output is correct
7 Correct 30 ms 8816 KB Output is correct
8 Correct 26 ms 8828 KB Output is correct
9 Correct 23 ms 8864 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 29 ms 8788 KB Output is correct
13 Correct 24 ms 8804 KB Output is correct
14 Correct 25 ms 8780 KB Output is correct
15 Correct 23 ms 8836 KB Output is correct
16 Correct 30 ms 8768 KB Output is correct
17 Correct 27 ms 8788 KB Output is correct
18 Correct 24 ms 8740 KB Output is correct
19 Runtime error 45 ms 5796 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 43 ms 5712 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 852 KB Output is correct
2 Runtime error 44 ms 5836 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -