Submission #1087945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087945		coldbr3w	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	255 ms	63432 KiB

event2

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,k;
ll up[N][20];
struct ccjv{ll l,r,idx;} a[N];
struct segment_tree_max{
    ll n;
    vector<ll>st, lz;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            st[id] = max(st[id], val);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st;
map<ll,ll>mp;
void build(){
	sort(a + 1, a + n + 1, [&](const ccjv &a, const ccjv &b){
		return a.l < b.l;
	});
	st.init(2 * n);
	ll j = 1;
	for(int i = 1; i <= 2 * n;i++){
		while(j <= n && a[j].l <= i) st.update(a[j].r, a[j].r, a[j].l), j++;
		up[i][0] = st.get(1, i);
	}
	for(int j = 1; j <= 19;j++){
		for(int i = 1; i <= 2 * n;i++) up[i][j] = up[up[i][j-1]][j-1];
	}
	sort(a + 1, a + n + 1, [&](const ccjv &a, const ccjv &b){
		return a.idx < b.idx;
	});
}
ll calc(ll l, ll r){
	ll res = 0;
	for(int i = 19; i >= 0;i--){
		if(up[r][i] >= l) r = up[r][i], res += (1 << i);
	}
	return res;
}
void to_thic_cau(){
	cin >> n >> k;
	vector<ll>v;
	for(int i = 1; i <= n;i++){
		cin >> a[i].l >> a[i].r; a[i].idx = i;
		v.pb(a[i].l); v.pb(a[i].r);
	}
	sort(all(v)); v.erase(unique(all(v)), v.end());
	for(int i = 0; i < v.size();i++) mp[v[i]] = i + 1;
	for(int i = 1; i <= n;i++) a[i].l = mp[a[i].l], a[i].r = mp[a[i].r];
	set<pll>s;
	build();
	ll cur = calc(1, 2 * n);
	if(cur < k){
		cout << -1 << '\n';
		return;
	}
	vector<ll>ans;
	for(int i = 1; i <= n;i++){
		if((ll)ans.size() == k) break;
		ll L, R, ok = 1;
		auto it = s.lower_bound({a[i].r, -inf});
		if(it == s.end()) R = 2 * n;
		else R = (*it).F;
		if(it != s.begin()){
			--it;
			L = (*it).S;
			if(L > a[i].l) ok = 0;
		}
		else L = 1;
		if(!ok) continue;
		if(cur - calc(L, R) + 1 + calc(L, a[i].l) + calc(a[i].r, R) >= k){
			cur = cur - calc(L, R) + 1 + calc(L, a[i].l) + calc(a[i].r, R);
			ans.pb(i);
			s.insert({a[i].l, a[i].r});
		}
	}
	for(auto x : ans) cout << x << '\n';
}

signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Compilation message (stderr)

event2.cpp: In function 'void to_thic_cau()':
event2.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < v.size();i++) mp[v[i]] = i + 1;
      |                 ~~^~~~~~~~~~

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