Submission #387956

#	Time	Username	Problem	Language	Result	Execution time	Memory
387956		SorahISA	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	3063 ms	4576 KiB

event2

#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)

template<typename T>
ostream& operator << (ostream &os, vector<T> vec) {
    for (int i = 0; i < vec.size(); ++i) {
        if (i) os << "\n";
        os << vec[i];
    }
    return os;
}

const int maxn = 2E5 + 5;

#define BUILD_BUG_ON_ZERO(e) void __(){return int : !!(e);}

int n, k;
vector<int> allVal, used(maxn, 0), pre(maxn);
vector<pii> ev, perm;

int countAnswer() {
    int r_bound = 0, res = 0;
    for (int i = 0; i < n; ++i) {
        int id = perm[i].Y;
        if (pre[ev[id].Y] - pre[ev[id].X] or ev[id].X < r_bound) continue;
        ++res, r_bound = ev[id].Y;
    }
    return res;
}

void solve() {
    cin >> n >> k, ev.resize(n), perm.resize(n);
    
    /// discretization ///
    
    for (auto &[l, r] : ev) cin >> l >> r, allVal.eb(l), allVal.eb(r);
    sort(ALL(allVal));
    allVal.resize(unique(ALL(allVal)) - begin(allVal));
    for (auto &[l, r] : ev) {
        l = lower_bound(ALL(allVal), l) - begin(allVal);
        r = lower_bound(ALL(allVal), r) - begin(allVal);
    }
    for (int i = 0; i < n; ++i) perm[i] = {ev[i].Y, i};
    sort(ALL(perm));
    
    // for (auto [l, r] : ev) cout << l << " " << r << "\n";
    
    if (countAnswer() < k) return cout << -1 << "\n", void();
    
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (pre[ev[i].Y] - pre[ev[i].X]) continue;
        for (int j = ev[i].X+1; j <= ev[i].Y; ++j) ++used[j];
        partial_sum(ALL(used), begin(pre));
        if (countAnswer() + ans.size() + 1 >= k) {ans.eb(i+1); continue;}
        for (int j = ev[i].X+1; j <= ev[i].Y; ++j) --used[j];
        partial_sum(ALL(used), begin(pre));
    }
    ans.resize(k);
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    while (t--) solve();
    
    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'void solve()':
event2.cpp:69:44: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if (countAnswer() + ans.size() + 1 >= k) {ans.eb(i+1); continue;}
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
event2.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>) [with T = int; std::ostream = std::basic_ostream<char>]':
event2.cpp:74:13:   required from here
event2.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < vec.size(); ++i) {

• Subtask 1: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 0 / 61