Submission #589564

#	Time	Username	Problem	Language	Result	Execution time	Memory
589564		Peti	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	104 ms	24140 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 l, 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] > -1 && st[i][x] < n && l < v[st[i][x]].l && 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;
    }

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

    vector<int> utan(n);
    while (!pq.empty()) pq.pop();
    sort(v.begin(), v.end(), [](inter a, inter b) -> bool{ return a.r > b.r; });
    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>> stelott(logn, vector<int>(n)), stutan(logn, vector<int>(n));
    stelott[0] = elott;
    stutan[0] = utan;

    calc(stelott, n);
    calc(stutan, n);

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

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

    int legk = 0;
    for(int i = 1; i < n; i++)
        if(v[i].r < v[legk].r)
            legk = i;

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

    for(int i = 0; i < n && 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 ind = prev(it)->ind != -1 ? prev(it)->ind : legk;
        int tmp = get(v, stutan, n, ind, prev(it)->r, it->l);
        if(prev(it)->r <= v[ind].l && v[ind].r <= it->l) tmp++;

        int db = get(v, stelott, n, i, prev(it)->r, it->l) + get(v, stutan, n, i, prev(it)->r, it->l);

        //cout<<i<<' '<<ind<<' '<<tmp<<' '<<db<<' '<<maxdb<<' '<<ki.size()<<" | "<<legk<<'\n';

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

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

    return 0;
}

/*
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:105:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |     for(int i = 0; i < n && ki.size() < k; i++){
      |                             ~~~~~~~~~~^~~
event2.cpp:124:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  124 |     if(ki.size() < k){
      |        ~~~~~~~~~~^~~

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