Submission #722538

#	Time	Username	Problem	Language	Result	Execution time	Memory
722538		minhnhatnoe	Event Hopping 2 (JOI21_event2)	C++14	32 / 100	3070 ms	5012 KiB

event2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> l;
struct node{
    int left, right;
    int idx;
};
vector<int> pos;
vector<node> a;
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);
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    l.resize(n), a.resize(n);
    for (int i=0; i<n; i++){
        cin >> a[i].left >> a[i].right;
        a[i].idx = 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();
    }
    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(n, -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 'int main()':
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:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i=0; i<a.size(); i++){
      |                       ~^~~~~~~~~
event2.cpp:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i=0; i<pos.size(); i++){
      |                       ~^~~~~~~~~~~

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