Submission #722545

#	Time	Username	Problem	Language	Result	Execution time	Memory
722545		minhnhatnoe	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	1 ms	328 KiB

event2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    int left, right;
    int idx;
};
vector<int> pos;
vector<node> a;
int n, k;
int test(int l, int r){
    int cnt = 0;
    int ptr = 0;
    for (int i=0; i<a.size(); i++){
        if (a[i].idx == -1) continue;
        int rinter = min(a[i].right, r);
        int linter = max(a[i].left, l);
        if (linter < rinter) continue;
        if (a[i].left < ptr) continue;
        cnt++;
        ptr = a[i].right;
    }
    return cnt;
}
void erase_inter(int l, int r){
    vector<node> nxta;
    for (int i=0; i<a.size(); i++){
        int rinter = min(a[i].right, r);
        int linter = max(a[i].left, l);
        if (linter < rinter) continue;
        nxta.push_back(a[i]);
    }
    a = move(nxta);
}
void get_input(){
    cin >> n >> k;
    a.resize(n);
    for (int i=0; i<n; i++){
        cin >> a[i].left >> a[i].right;
        a[i].idx = i;
    }
    sort(a.begin(), a.end(), [](const node &x, const node &y){
        return pair(x.left, -x.right) < pair(y.left, -y.right);
    });
    vector<node> nxta;
    for (int i=0; i<a.size(); i++){
        while (nxta.size() && nxta.back().right >= a[i].right) nxta.pop_back();
        nxta.push_back(a[i]);
    }
    a = move(nxta);
    vector<int> l(a.size());
    for (int i=0; i<a.size(); i++) l[i] = a[i].left;
    sort(l.begin(), l.end());
    l.resize(unique(l.begin(), l.end()) - l.begin());
    for (int i=0; i<a.size(); i++){
        a[i].left = lower_bound(l.begin(), l.end(), a[i].left) - l.begin();
        a[i].right = lower_bound(l.begin(), l.end(), a[i].right) - l.begin();
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    get_input();
    sort(a.begin(), a.end(), [](const node &x, const node &y){
        return x.right < y.right;
    });
    if (test(-1, -1) < k){
        cout << "-1\n";
        return 0;
    }
    while (k){
        pos.assign(a.size(), -1);
        for (int i=0; i<a.size(); i++){
            if (a[i].idx == -1) continue;
            pos[a[i].idx] = i;
        }
        for (int i=0; i<pos.size(); i++){
            if (pos[i] == -1) continue;
            if (test(a[pos[i]].left, a[pos[i]].right) + 1 < k){
                a[pos[i]].idx = -1;
                continue;
            }
            a[pos[i]].idx = -1;
            erase_inter(a[pos[i]].left, a[pos[i]].right);
            cout << i+1 << "\n";
            break;
        }
        k--;
    }
}

Compilation message (stderr)

event2.cpp: In function 'int test(int, int)':
event2.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp: In function 'void erase_inter(int, int)':
event2.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp: In function 'void get_input()':
event2.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i=0; i<a.size(); i++) l[i] = a[i].left;
      |                   ~^~~~~~~~~
event2.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0; i<a.size(); i++){
      |                   ~^~~~~~~~~
event2.cpp: In function 'int main()':
event2.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i=0; i<a.size(); i++){
      |                       ~^~~~~~~~~
event2.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i=0; i<pos.size(); i++){
      |                       ~^~~~~~~~~~~

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