oj.uz

Submission #387949

# Submission time Handle Problem Language Result Execution time Memory
387949 2021-04-09T14:55:14 Z SorahISA Event Hopping 2 (JOI21_event2) C++17
0 / 100
 3000 ms 6256 KB 
#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-1] 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) + 1;
        r = lower_bound(ALL(allVal), r) - begin(allVal) + 1;
    }
    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-1]) continue;
        for (int j = ev[i].X; 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; 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1792 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Execution timed out 3052 ms 6256 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1872 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1900 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 3 ms 1868 KB Output is correct
9 Correct 2 ms 1900 KB Output is correct
10 Correct 2 ms 1900 KB Output is correct
11 Correct 1 ms 1872 KB Output is correct
12 Correct 2 ms 1868 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 3 ms 1868 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Incorrect 6 ms 1868 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1872 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1900 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 3 ms 1868 KB Output is correct
9 Correct 2 ms 1900 KB Output is correct
10 Correct 2 ms 1900 KB Output is correct
11 Correct 1 ms 1872 KB Output is correct
12 Correct 2 ms 1868 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 3 ms 1868 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Incorrect 6 ms 1868 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1792 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Execution timed out 3052 ms 6256 KB Time limit exceeded
5 Halted 0 ms 0 KB -