oj.uz

Submission #595579

# Submission time Handle Problem Language Result Execution time Memory
595579 2022-07-13T20:41:18 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 20656 KB 
#include <bits/stdc++.h>
#define MAX 200005
int N,Q;
typedef std::pair<int,int> pii;
std::vector<pii> eventos;

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

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

int tab[MAX*4];

int query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    if(la>r||ra<l)return 1e9;
    if(la>=l&&ra<=r){
        return tab[pos];
    }
    int m = (la+ra)/2;
    return std::min(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}

void update(int t,int k,int la=0,int ra=MAX-1,int pos=1){
    if(la>t||ra<t)return;
    if(la==ra){
        tab[pos]=std::min(tab[pos],k);
        return;
    }
    int m = (la+ra)/2;
    update(t,k,la,m,pos*2);
    update(t,k,m+1,ra,(pos*2)+1);
    tab[pos]=std::min(tab[pos*2],tab[(pos*2)+1]);
}

void zerar(void){for(auto&x:tab)x=1e9;}

typedef std::pair<int,int*> pipo;
int custos[MAX];
void simula(int x){
    zerar();
    for(auto&x:custos)x=1e9;
    update(eventos[x].second,1);
    for(int i=0;i!=MAX;++i){
        int minimo=1e9;
        for(auto&x:rem[i]){
            int d = query(eventos[x].first,eventos[x].second);
            update(eventos[x].second,d+1);
            custos[x]=d;
            minimo=std::min(minimo,d+1);
        }
        for(auto&x:rem[i]){
            custos[x]=std::min(custos[x],minimo);
        }
    }
    custos[x]=0;
}
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;
        }
    }
    for(int i=0;i!=N;++i){
        add[eventos[i].first].push_back(i);
        rem[eventos[i].second].push_back(i);
    }
    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 9 ms 13524 KB Output is correct
2 Execution timed out 1572 ms 20620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13508 KB Output is correct
2 Correct 11 ms 13528 KB Output is correct
3 Correct 124 ms 13684 KB Output is correct
4 Correct 153 ms 13688 KB Output is correct
5 Correct 164 ms 13652 KB Output is correct
6 Correct 134 ms 13688 KB Output is correct
7 Correct 138 ms 13680 KB Output is correct
8 Correct 150 ms 13684 KB Output is correct
9 Correct 112 ms 13688 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13508 KB Output is correct
2 Correct 11 ms 13528 KB Output is correct
3 Correct 124 ms 13684 KB Output is correct
4 Correct 153 ms 13688 KB Output is correct
5 Correct 164 ms 13652 KB Output is correct
6 Correct 134 ms 13688 KB Output is correct
7 Correct 138 ms 13680 KB Output is correct
8 Correct 150 ms 13684 KB Output is correct
9 Correct 112 ms 13688 KB Output is correct
10 Correct 8 ms 13524 KB Output is correct
11 Correct 12 ms 13524 KB Output is correct
12 Correct 146 ms 13684 KB Output is correct
13 Correct 128 ms 13684 KB Output is correct
14 Correct 117 ms 13680 KB Output is correct
15 Correct 136 ms 13684 KB Output is correct
16 Correct 150 ms 13680 KB Output is correct
17 Correct 124 ms 13652 KB Output is correct
18 Correct 98 ms 13684 KB Output is correct
19 Execution timed out 1581 ms 13888 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13508 KB Output is correct
2 Correct 11 ms 13528 KB Output is correct
3 Correct 124 ms 13684 KB Output is correct
4 Correct 153 ms 13688 KB Output is correct
5 Correct 164 ms 13652 KB Output is correct
6 Correct 134 ms 13688 KB Output is correct
7 Correct 138 ms 13680 KB Output is correct
8 Correct 150 ms 13684 KB Output is correct
9 Correct 112 ms 13688 KB Output is correct
10 Correct 8 ms 13524 KB Output is correct
11 Correct 11 ms 13524 KB Output is correct
12 Correct 108 ms 13696 KB Output is correct
13 Correct 124 ms 13688 KB Output is correct
14 Correct 115 ms 13684 KB Output is correct
15 Correct 110 ms 13652 KB Output is correct
16 Correct 124 ms 13684 KB Output is correct
17 Correct 121 ms 13652 KB Output is correct
18 Correct 107 ms 13684 KB Output is correct
19 Execution timed out 1569 ms 20656 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 1578 ms 20636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13524 KB Output is correct
2 Execution timed out 1572 ms 20620 KB Time limit exceeded
3 Halted 0 ms 0 KB -