Submission #589652

#	Time	Username	Problem	Language	Result	Execution time	Memory
589652		Peti	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	196 ms	18868 KiB

event2

#include <bits/stdc++.h>

using namespace std;

struct inter{
    int l, r, ind;
    bool operator<(const inter &in) const{
        if(l != in.l) return l < in.l;
        return r < in.r;
    }
};

const int logn = 20;

void calc(vector<vector<int>> &st, int n){
    for(int i = 1; i < logn; i++){
        for(int j = 0; j < n; j++){
            if(st[i-1][j] > -1 && st[i-1][j] < n) st[i][j] = st[i-1][st[i-1][j]];
            else st[i][j] = st[i-1][j];
        }
    }
}

int get(vector<inter> &v, vector<vector<int>> &st, int n, int x, int r){
    int ret = 0;
    for(int i = logn-1; i >= 0 && x > -1 && x < n; i--){
        //cout<<x<<' '<<i<<' '<<st[i][x]<<'\n';
        if(st[i][x] < n && v[st[i][x]].r <= r){
            ret += (1<<i);
            x = st[i][x];
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin>>n>>k;

    vector<inter> v(n);
    for(int i = 0; i < n; i++){
        cin>>v[i].l>>v[i].r;
        v[i].ind = i;
    }
    v.push_back({-2, -1, n});
    n++;

    vector<int> utan(n);
    priority_queue<pair<int, int>> pq;
    sort(v.begin(), v.end(), [](inter a, inter b) -> bool{ return a.r > b.r; });
    int last = -1;
    for(int i = 0; i < n; i++){
        pq.push({v[i].l, i});
        while(!pq.empty() && pq.top().first >= v[i].r){
            if(last == -1 || v[last].r > v[pq.top().second].r) last = pq.top().second;
            pq.pop();
        }
        utan[v[i].ind] = last != -1 ? v[last].ind : n;
    }

    sort(v.begin(), v.end(), [](inter a, inter b) -> bool{ return a.ind < b.ind; });

    /*cout<<"elott: \n";
    for(int i = 0; i < n; i++) cout<<i<<' '<<elott[i]<<'\n';
    cout<<"utan: \n";
    for(int i =0; i < n; i++) cout<<i<<' '<<utan[i]<<'\n';*/

    vector<vector<int>> stutan(logn, vector<int>(n));
    stutan[0] = utan;

    calc(stutan, n);

    /*cout<<"stutan: ";
    for(int i = 0; i < n; i++) cout<<stutan[1][i]<<' ';
    cout<<'\n';*/

    set<inter> s;
    s.insert({-2, -1, n-1});
    s.insert({(int)1e9+1, (int)1e9+1, -1});
    vector<int> ki;

    int maxdb = get(v, stutan, n, n-1, (int)1e9+1);

    if(maxdb < k){
        cout<<-1<<'\n';
        return 0;
    }

    //for(int i = 0; i < logn; i++) cout<<stutan[i][n-1]<<'\n';

    for(int i = 0; i < n-1 && ki.size() < k; i++){
        auto it = s.lower_bound(v[i]);
        if(prev(it)->r > v[i].l || v[i].r > it->l) continue;

        int tmp = get(v, stutan, n, prev(it)->ind, it->l);
        int db = get(v, stutan, n, prev(it)->ind, v[i].l) + get(v, stutan, n, i, it->l);

        //cout<<i<<" | "<<tmp<<' '<<db<<' '<<maxdb<<' '<<ki.size()<<" | "<<prev(it)->ind<<'\n';

        if((int)ki.size() + maxdb - tmp + db + 1 >= k){
            ki.push_back(i+1);
            s.insert(v[i]);
            maxdb -= tmp - db;
            //cout<<"berak\n";
            //cout<<"uj: "<<maxdb<<'\n';
        }
    }

    if(ki.size() < k){
        cout<<-1<<'\n';
    } else{
        for(int x : ki) cout<<x<<'\n';
    }

    return 0;
}

/*
5 4
1 3
2 5
8 9
6 8
10 15


10 6
1 2
2 3
2 4
4 5
4 6
6 7
7 8
8 9
9 10
10 11
*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:94:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     for(int i = 0; i < n-1 && ki.size() < k; i++){
      |                               ~~~~~~~~~~^~~
event2.cpp:112:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     if(ki.size() < k){
      |        ~~~~~~~~~~^~~

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