oj.uz

Submission #595529

# Submission time Handle Problem Language Result Execution time Memory
595529 2022-07-13T19:47:04 Z ThegeekKnight16 Event Hopping (BOI22_events) C++14
30 / 100
 855 ms 18520 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int Inicio[MAXN], Fim[MAXN], Marc[MAXN];
vector<int> Indices;
int dp[MAXN][25];
int prox[MAXN];

bool cmp(int a, int b)
{
    if (Fim[a] == Fim[b]) return Inicio[a] < Inicio[b];
    return Fim[a] > Fim[b];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
    {
        cin >> Inicio[i] >> Fim[i];
        Indices.push_back(i);
    }
    sort(Indices.begin(), Indices.end(), cmp);
    vector<int> Usados, naoUsados;
    
    int L = 1e9 + 10; int Encima = -1;
    for (auto id : Indices)
    {
        if (Inicio[id] >= L) {naoUsados.push_back(id); prox[id] = Encima;}
        else
        {
            Usados.push_back(id);
            L = Inicio[id];
            Marc[id] = 1;
            Encima = id;
        }
    }
    
    int p = 0;
    for (int i = 0; i < Usados.size(); i++)
    {
        int id = Usados[i]; int pd = Usados[p];
        while (p < i && Fim[id] < Inicio[Usados[p]]) pd = Usados[++p];
        cerr << id << " " << pd << '\n';
        
        if (Fim[id] < Inicio[pd] || Fim[id] > Fim[pd] || id == pd) prox[id] = N+1;
        else prox[id] = pd;
    }
    
    prox[N+1] = N+1; Fim[N+1] = 1e9 + 10; Inicio[N+1] = 1e9 + 10;
    for (int i = 1; i <= N+1; i++) {dp[i][0] = prox[i]; cerr << prox[i] << " ";}
    for (int k = 1; k <= 20; k++)
    {
        for (int i = 1; i <= N+1; i++)
        {
            dp[i][k] = dp[ dp[i][k-1] ][k-1];
        }
    }
    
    for (int q = 1; q <= Q; q++)
    {
        int X, Y;
        cin >> X >> Y;
        
        int D = X; int resp = 0;
        for (int k = 20; k >= 0; k--)
        {
            int id = dp[D][k];
            if (Fim[id] <= Fim[Y])
            {
                D = id;
                resp += (1 << k);
            }
        }
        
        if (Fim[D] < Inicio[Y] || Fim[D] > Fim[Y]) cout << "impossible" << '\n';
        else
        {
            if (D != Y) resp++;
            cout << resp << '\n';
        }
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < Usados.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 855 ms 16164 KB Output is correct
3 Correct 851 ms 18060 KB Output is correct
4 Correct 830 ms 17856 KB Output is correct
5 Correct 742 ms 17968 KB Output is correct
6 Correct 721 ms 18164 KB Output is correct
7 Correct 699 ms 18136 KB Output is correct
8 Correct 340 ms 16924 KB Output is correct
9 Correct 770 ms 18508 KB Output is correct
10 Correct 791 ms 18464 KB Output is correct
11 Correct 620 ms 18164 KB Output is correct
12 Correct 561 ms 17400 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 500 KB Output is correct
4 Correct 8 ms 396 KB Output is correct
5 Incorrect 3 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 500 KB Output is correct
4 Correct 8 ms 396 KB Output is correct
5 Incorrect 3 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 7 ms 500 KB Output is correct
4 Correct 8 ms 396 KB Output is correct
5 Incorrect 3 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 15264 KB Output is correct
2 Correct 787 ms 18056 KB Output is correct
3 Correct 837 ms 17768 KB Output is correct
4 Correct 774 ms 18520 KB Output is correct
5 Correct 802 ms 18256 KB Output is correct
6 Correct 808 ms 18092 KB Output is correct
7 Correct 821 ms 18100 KB Output is correct
8 Correct 795 ms 18264 KB Output is correct
9 Correct 730 ms 16284 KB Output is correct
10 Correct 786 ms 17788 KB Output is correct
11 Correct 803 ms 17568 KB Output is correct
12 Correct 785 ms 17656 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 855 ms 16164 KB Output is correct
3 Correct 851 ms 18060 KB Output is correct
4 Correct 830 ms 17856 KB Output is correct
5 Correct 742 ms 17968 KB Output is correct
6 Correct 721 ms 18164 KB Output is correct
7 Correct 699 ms 18136 KB Output is correct
8 Correct 340 ms 16924 KB Output is correct
9 Correct 770 ms 18508 KB Output is correct
10 Correct 791 ms 18464 KB Output is correct
11 Correct 620 ms 18164 KB Output is correct
12 Correct 561 ms 17400 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 7 ms 500 KB Output is correct
16 Correct 8 ms 396 KB Output is correct
17 Incorrect 3 ms 468 KB Output isn't correct
18 Halted 0 ms 0 KB -