oj.uz

Submission #595578

# Submission time Handle Problem Language Result Execution time Memory
595578 2022-07-13T20:39:49 Z Deepesson Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 20672 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){
        for(auto&x:rem[i]){
            int d = query(eventos[x].first,eventos[x].second);
            update(eventos[x].second,d+1);
            custos[x]=d;
        }
        for(auto&x:rem[i]){
            int d = query(eventos[x].first,eventos[x].second);
            update(eventos[x].second,d+1);
            custos[x]=std::min(custos[x],d);
        }
    }
    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 12 ms 13524 KB Output is correct
2 Execution timed out 1562 ms 20640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13516 KB Output is correct
2 Correct 14 ms 13624 KB Output is correct
3 Correct 155 ms 13616 KB Output is correct
4 Correct 149 ms 13688 KB Output is correct
5 Correct 122 ms 13652 KB Output is correct
6 Correct 136 ms 13664 KB Output is correct
7 Correct 210 ms 13652 KB Output is correct
8 Correct 162 ms 13652 KB Output is correct
9 Correct 125 ms 13684 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13516 KB Output is correct
2 Correct 14 ms 13624 KB Output is correct
3 Correct 155 ms 13616 KB Output is correct
4 Correct 149 ms 13688 KB Output is correct
5 Correct 122 ms 13652 KB Output is correct
6 Correct 136 ms 13664 KB Output is correct
7 Correct 210 ms 13652 KB Output is correct
8 Correct 162 ms 13652 KB Output is correct
9 Correct 125 ms 13684 KB Output is correct
10 Correct 8 ms 13536 KB Output is correct
11 Correct 11 ms 13520 KB Output is correct
12 Correct 166 ms 13688 KB Output is correct
13 Correct 201 ms 13596 KB Output is correct
14 Correct 147 ms 13684 KB Output is correct
15 Correct 136 ms 13652 KB Output is correct
16 Correct 212 ms 13688 KB Output is correct
17 Correct 193 ms 13700 KB Output is correct
18 Correct 137 ms 13688 KB Output is correct
19 Execution timed out 1576 ms 13872 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13516 KB Output is correct
2 Correct 14 ms 13624 KB Output is correct
3 Correct 155 ms 13616 KB Output is correct
4 Correct 149 ms 13688 KB Output is correct
5 Correct 122 ms 13652 KB Output is correct
6 Correct 136 ms 13664 KB Output is correct
7 Correct 210 ms 13652 KB Output is correct
8 Correct 162 ms 13652 KB Output is correct
9 Correct 125 ms 13684 KB Output is correct
10 Correct 8 ms 13524 KB Output is correct
11 Correct 14 ms 13596 KB Output is correct
12 Correct 143 ms 13688 KB Output is correct
13 Correct 163 ms 13680 KB Output is correct
14 Correct 175 ms 13652 KB Output is correct
15 Correct 151 ms 13652 KB Output is correct
16 Correct 150 ms 13684 KB Output is correct
17 Correct 161 ms 13688 KB Output is correct
18 Correct 140 ms 13684 KB Output is correct
19 Execution timed out 1580 ms 20660 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 1580 ms 20672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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