oj.uz

Submission #595607

# Submission time Handle Problem Language Result Execution time Memory
595607 2022-07-13T21:36:26 Z Deepesson Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 108812 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;
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);
        }
      //  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;
    }
    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 5 ms 9684 KB Output is correct
2 Execution timed out 1584 ms 14732 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 6 ms 9684 KB Output is correct
3 Correct 34 ms 17664 KB Output is correct
4 Correct 38 ms 17676 KB Output is correct
5 Correct 30 ms 17740 KB Output is correct
6 Correct 29 ms 17668 KB Output is correct
7 Correct 40 ms 17660 KB Output is correct
8 Correct 38 ms 17724 KB Output is correct
9 Correct 22 ms 17636 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 6 ms 9684 KB Output is correct
3 Correct 34 ms 17664 KB Output is correct
4 Correct 38 ms 17676 KB Output is correct
5 Correct 30 ms 17740 KB Output is correct
6 Correct 29 ms 17668 KB Output is correct
7 Correct 40 ms 17660 KB Output is correct
8 Correct 38 ms 17724 KB Output is correct
9 Correct 22 ms 17636 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 29 ms 17732 KB Output is correct
13 Correct 34 ms 17740 KB Output is correct
14 Correct 36 ms 17820 KB Output is correct
15 Correct 29 ms 17688 KB Output is correct
16 Correct 39 ms 17732 KB Output is correct
17 Correct 32 ms 17744 KB Output is correct
18 Correct 21 ms 17720 KB Output is correct
19 Correct 646 ms 108420 KB Output is correct
20 Correct 650 ms 108328 KB Output is correct
21 Correct 682 ms 108812 KB Output is correct
22 Correct 628 ms 108748 KB Output is correct
23 Correct 905 ms 108492 KB Output is correct
24 Correct 730 ms 108504 KB Output is correct
25 Correct 1000 ms 108212 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 6 ms 9684 KB Output is correct
3 Correct 34 ms 17664 KB Output is correct
4 Correct 38 ms 17676 KB Output is correct
5 Correct 30 ms 17740 KB Output is correct
6 Correct 29 ms 17668 KB Output is correct
7 Correct 40 ms 17660 KB Output is correct
8 Correct 38 ms 17724 KB Output is correct
9 Correct 22 ms 17636 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 29 ms 17644 KB Output is correct
13 Correct 34 ms 17664 KB Output is correct
14 Correct 30 ms 17744 KB Output is correct
15 Correct 29 ms 17732 KB Output is correct
16 Correct 41 ms 17680 KB Output is correct
17 Correct 31 ms 17740 KB Output is correct
18 Correct 26 ms 17732 KB Output is correct
19 Correct 810 ms 14744 KB Output is correct
20 Correct 474 ms 15876 KB Output is correct
21 Correct 418 ms 16328 KB Output is correct
22 Correct 438 ms 16600 KB Output is correct
23 Correct 493 ms 16592 KB Output is correct
24 Correct 1034 ms 16652 KB Output is correct
25 Correct 174 ms 16004 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 14736 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 1584 ms 14732 KB Time limit exceeded
3 Halted 0 ms 0 KB -