Submission #934138

#	Time	Username	Problem	Language	Result	Execution time	Memory
934138		velislavgarkov	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	145 ms	51052 KiB

event2

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;
const int MAXN=4e5+10;
#define endl '\n'
struct Range {
    int l, r;
    int ind;
    bool friend operator < (Range a, Range b) {
        return a.r<b.r;
    }
};
struct Hole {
    int l, r, res;
    bool friend operator < (Hole a, Hole b) {
        return a.r<b.r;
    }
};
Range e[MAXN], og[MAXN];
int points[MAXN];
unordered_map <int,int> um;
vector <int> ans;
set <Hole> s;
int sp[2][MAXN][20], cnt;
int n, k;
void sparce_table() {
    for (int i=1;(1<<i)<=n;i++) {
        for (int j=1;j+(1<<i)-1<=n;j++) {
            sp[0][j][i]=max(sp[0][j][i-1], sp[0][j + (1 << (i-1))][i-1]);
        }
    }
}
void sparce_tree() {
    for (int i=1;(1<<i)<=cnt;i++) {
        for (int j=0;j<=cnt;j++) {
            if (sp[1][j][i-1]==0) continue;
            sp[1][j][i]=sp[1][sp[1][j][i-1]][i-1];
        }
    }
}
int find_dist(int cur, int gr) {
    int st=18, res=0;
    while (st>=0) {
        if (sp[1][cur][st]!=0 && sp[1][cur][st]<=gr) {
            cur=sp[1][cur][st];
            res+=(1<<st);
        }
        st--;
    }
    return res;
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        cin >> e[i].l >> e[i].r;
        e[i].ind=i;
        points[2*i-1]=e[i].l;
        points[2*i]=e[i].r;
    }
    sort(points+1,points+2*n+1);
    cnt=1;
    for (int i=1;i<=2*n;i++) {
        if (um[points[i]]!=0) continue;
        um[points[i]]=cnt;
        cnt++;
    }
    for (int i=1;i<=n;i++) {
        e[i].l=um[e[i].l];
        e[i].r=um[e[i].r];
        og[i]=e[i];
    }
    sort(e+1,e+n+1);
    for (int i=1;i<=n;i++) sp[0][i][0]=e[i].l;
    sparce_table();
    for (int i=n-1;i>=1;i--) {
        if (e[i].r==e[i+1].r) continue;
        int st=18, j=i+1;
        if (e[j].l<e[i].r) {
            while (st>=0) {
                if (j+(1<<st)-1<=n && sp[0][j][st]<e[i].r) j+=(1<<st);
                st--;
            }
        }
        sp[1][e[i].r][0]=e[j].r;
    }
    sp[1][0][0]=e[1].r;
    sparce_tree();
    s.insert({0,cnt+1,k});
    int cur_sum=k;
    for (int i=1;i<=n;i++) {
        auto it=s.lower_bound({og[i].r,og[i].r,1});
        if ((*it).l>og[i].l) continue;
        int curl, curr;
        curl=(*it).l; curr=(*it).r;
        int lef=find_dist(curl,og[i].l);
        int ri=find_dist(og[i].r,curr);
        if (lef+ri+1+cur_sum-(*it).res>=k) {
            cur_sum-=(*it).res;
            cur_sum+=lef+ri+1;
            ans.push_back(i);
            s.erase(it);
            s.insert({curl,og[i].l,lef});
            s.insert({og[i].r,curr,ri});
        }
        if (ans.size()==k) break;
    }
    if (ans.size()<k) cout << -1 << endl;
    else for (auto i:ans) cout << i << endl;
    return 0;
}
/*
5 4
1 3
2 5
8 9
6 8
10 15
*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:110:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |         if (ans.size()==k) break;
      |             ~~~~~~~~~~^~~
event2.cpp:112:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     if (ans.size()<k) cout << -1 << endl;
      |         ~~~~~~~~~~^~

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