Submission #746775

#	Time	Username	Problem	Language	Result	Execution time	Memory
746775		nguyentunglam	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	274 ms	15912 KiB

event2

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N];
vector<pair<int, int> > line, tmp;
int f[20][N], lg;
int get(int x) {
    return lower_bound(line.begin(), line.end(), make_pair(x, 0)) - line.begin();
}
int calc(int l, int r) {
    int u = get(l), ret = 0;
    for(int j = lg; j >= 0; j--) if (f[j][u] > 0 && f[j][u] <= r) {
        u = get(f[j][u]);
        ret += 1 << j;
    }
    return ret;
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n, k; cin >> n >> k;
    lg = log2(n);
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        line.push_back(a[i]);
    }
    sort(line.begin(), line.end(), [] (const ii &x, const ii &y) {
         if (x.fi != y.fi) return x.fi < y.fi;
         return x.se > y.se;
         });
    int pre = 1e9;
    for(int i = line.size() - 1; ~i; i--) {
        int l, r; tie(l, r) = line[i];
        if (r < pre) {
            pre = r;
            tmp.push_back(line[i]);
        }
    }
    reverse(tmp.begin(), tmp.end());
    line = tmp;
    int m = line.size();
    for(int i = 0; i < m; i++) f[0][i] = line[i].second;
    for(int j = 1; j <= lg; j++) for(int i = 0; i < m; i++) {
        if (f[j - 1][i]) f[j][i] = f[j - 1][get(f[j - 1][i])];
    }


    set<pair<int, int> > s;
    s.insert({1, 1e9});
    int cur = calc(1, 1e9);
    int cnt = 0;
    if (cur < k) return cout << -1, 0;
    for(int i = 1; i <= n && cnt < k; i++) {
        auto it = s.upper_bound(make_pair(a[i].first, 1e9));
        if (it == s.begin()) continue;
        it--;
        if (it -> second < a[i].second) continue;
        int l, r; tie(l, r) = *it;
        int tmp = calc(l, a[i].first) + calc(a[i].second, r) + 1 - calc(l, r) + cur;
        if (tmp >= k) {
            s.erase(it);
            if (l < a[i].first) s.insert({l, a[i].first});
            if (a[i].second < r) s.insert({a[i].second, r});
            cout << i << endl;
            cnt++;
            cur = tmp;
        }
    }
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:26:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:27:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:30:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:31:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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