oj.uz

Submission #596240

# Submission time Handle Problem Language Result Execution time Memory
596240 2022-07-14T13:58:51 Z Deepesson Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 20132 KB 
#include <bits/stdc++.h>
#define MAX 200010
#define LSB(A) (A&(-A))
#define LOG 20
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];

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

int armazena[MAX];
int valor[MAX];
int jump[MAX][LOG];

void gera_conexoes(){
    for(int i=0;i!=N;++i){
        int max=1e9+1,pep=-1;
        int l = eventos[i].first,r=eventos[i].second;
        for(int i=0;i!=eventos.size();++i){
            auto x = eventos[i];
            if(x.second>=l&&x.second<=r){
                if(x.first<max){
                    max=x.first;
                    pep=i;
                }
            }
        }
        jump[i][0]=pep;
    }
}

int jumps(int a,int b){
    int pos = a;
    for(int i=LOG-1;i!=-1;--i){
        if(((1<<i)&b)&&jump[pos][i]!=-1){
            pos=jump[pos][i];
        }
    }
    return pos;
}

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){
        add[eventos[i].first].push_back(i);
        rem[eventos[i].second].push_back(i);
    }
    gera_conexoes();
   // for(int i=0;i!=N;++i)if(jump[i][0]==i)jump[i][0]=-1;
    for(int j=1;j!=LOG;++j){
        for(int i=0;i!=N;++i){
            if(jump[i][j-1]==-1)jump[i][j]=-1;
            else
            jump[i][j]=jump[jump[i][j-1]][j-1];
        }
    }

    for(int i=0;i!=Q;++i){
        int s,t;
        std::cin>>s>>t;
        --s;--t;
        if(s==t){
            std::cout<<"0\n";
            continue;
        }
        if(eventos[t].second<eventos[s].second){
            std::cout<<"impossible\n";
            continue;
        }
        int cord = eventos[s].second;

        int l=0,r=1e9;
        while(l<r){
            int m = (l+r)/2;
            int q=jumps(t,m);
            if(eventos[q].first<=cord){
                r=m;
            }else l=m+1;
        }
       // std::cout<<"ve "<<l<<"\n";
        int q=jumps(t,l);
        if(q!=s){
            ++l;
        }
      //  std::cout<<"Val R: "<<r<<"\n";
        if(r==1e9){
            std::cout<<"impossible\n";
            continue;
        }
        std::cout<<l<<"\n";
    }
}

Compilation message

events.cpp: In function 'void gera_conexoes()':
events.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i=0;i!=eventos.size();++i){
      |                     ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1578 ms 17932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 11 ms 9840 KB Output is correct
4 Correct 12 ms 9900 KB Output is correct
5 Correct 10 ms 9888 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 15 ms 9872 KB Output is correct
8 Correct 10 ms 9812 KB Output is correct
9 Correct 8 ms 9876 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 11 ms 9840 KB Output is correct
4 Correct 12 ms 9900 KB Output is correct
5 Correct 10 ms 9888 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 15 ms 9872 KB Output is correct
8 Correct 10 ms 9812 KB Output is correct
9 Correct 8 ms 9876 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 7 ms 9876 KB Output is correct
14 Correct 7 ms 9892 KB Output is correct
15 Correct 7 ms 9876 KB Output is correct
16 Correct 9 ms 9812 KB Output is correct
17 Correct 9 ms 9812 KB Output is correct
18 Correct 8 ms 9812 KB Output is correct
19 Correct 197 ms 11728 KB Output is correct
20 Correct 129 ms 11920 KB Output is correct
21 Correct 115 ms 12108 KB Output is correct
22 Correct 139 ms 12048 KB Output is correct
23 Correct 150 ms 12076 KB Output is correct
24 Correct 175 ms 12044 KB Output is correct
25 Correct 137 ms 11684 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 11 ms 9840 KB Output is correct
4 Correct 12 ms 9900 KB Output is correct
5 Correct 10 ms 9888 KB Output is correct
6 Correct 10 ms 9848 KB Output is correct
7 Correct 15 ms 9872 KB Output is correct
8 Correct 10 ms 9812 KB Output is correct
9 Correct 8 ms 9876 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9876 KB Output is correct
14 Correct 7 ms 9808 KB Output is correct
15 Correct 9 ms 9872 KB Output is correct
16 Correct 9 ms 9812 KB Output is correct
17 Correct 11 ms 9856 KB Output is correct
18 Correct 7 ms 9876 KB Output is correct
19 Execution timed out 1584 ms 20132 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 18676 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 1578 ms 17932 KB Time limit exceeded
3 Halted 0 ms 0 KB -