oj.uz

Submission #930616

# Submission time Handle Problem Language Result Execution time Memory
930616 2024-02-20T08:10:05 Z boris_mihov Event Hopping 2 (JOI21_event2) C++17
0 / 100
 78 ms 28488 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 20;
const int INF  = 2e9;

int n, k;
struct Sparse
{
    int sparse[MAXLOG][MAXN];
    void build(int jump[])
    {
        jump[2 * n + 1] = 2 * n + 1;
        for (int i = 1 ; i <= 2 * n + 1 ; ++i)
        {
            sparse[0][i] = jump[i];
        }

        for (int lg = 1 ; (1 << lg) <= 2 * n + 1 ; ++lg)
        {
            for (int idx = 1 ; idx <= 2 * n + 1 ; ++idx)
            {
                sparse[lg][idx] = sparse[lg - 1][sparse[lg - 1][idx]];   
            }
        }
    }

    int query(int l ,int r)
    {
        int pos = l;
        int cnt = 0;

        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (sparse[lg][pos] != 0 && sparse[lg][pos] <= r)
            {
                cnt += (1 << lg);
                pos = sparse[lg][pos];
            }
        }

        return cnt;
    }
};

int l[MAXN];
int r[MAXN];
int jump[MAXN];
int perm[MAXN];
Sparse sparse;
std::set <std::pair <int,int>> added;

void solve()
{
    std::vector <std::pair <int, std::pair <int,bool>>> v;
    for (int i = 1 ; i <= n ; ++i)
    {
        v.push_back({l[i], {i, false}});
        v.push_back({r[i], {i, true}});
    }
    
    int cnt = 0;
    int last = 0;
    std::sort(v.begin(), v.end());
    for (int i = 0 ; i < 2 * n ; ++i)
    {
        cnt += (v[i].first > last);
        last = v[i].first;
 
        if (v[i].second.second) r[v[i].second.first] = cnt;
        else l[v[i].second.first] = cnt;
    }

    std::fill(jump + 1, jump + 2 * n + 1, 2 * n + 1);
    for (int i = 1 ; i <= n ; ++i)
    {
        jump[l[i]] = std::min(jump[l[i]], r[i]);
    }

    for (int idx = 2 * n - 1 ; idx >= 1 ; --idx)
    {
        jump[idx] = std::min(jump[idx], jump[idx + 1]);
    }

    sparse.build(jump);
    if (sparse.query(1, 2 * n) < k)
    {
        std::cout << -1 << '\n';
        return;
    }

    added.insert({0, 0});
    added.insert({2 * n, 2 * n});
    std::vector <int> sol;

    int answer = sparse.query(1, 2 * n);
    for (int i = 1 ; i <= n && sol.size() < k ; ++i)
    {
        auto it = added.lower_bound({l[i], 0});
        if (it->first < r[i])
        {
            continue;
        }

        auto prev = std::prev(it);
        if (prev->second > l[i])
        {
            continue;
        }

        int curr = sparse.query(prev->second, l[i]) + sparse.query(r[i], it->first) - sparse.query(prev->second, it->first);
        if (answer + curr >= k)
        {
            answer += curr;
            sol.push_back(i);
            added.insert({l[i], r[i]});
        }
    }

    for (const int &idx : sol)
    {
        std::cout << idx << '\n';
    }
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

event2.cpp: In function 'void solve()':
event2.cpp:106:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     for (int i = 1 ; i <= n && sol.size() < k ; ++i)
      |                                ~~~~~~~~~~~^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6576 KB Output is correct
4 Incorrect 78 ms 28488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6576 KB Output is correct
4 Incorrect 78 ms 28488 KB Output isn't correct
5 Halted 0 ms 0 KB -