제출 #477491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477491		dennisstar	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	1045 ms	10736 KiB

event2

#include <bits/stdc++.h>

using namespace std;

const int B = 300;

struct myst {
	vector<pair<int, int>> p, nxt;
	void init() {
		int n=p.size();
		nxt.resize(n);
		for (int i=n-1; i>=0; i--) {
			auto b=lower_bound(p.begin(), p.end(), pair<int, int>(p[i].second, 0))-p.begin();
			if (b>=p.size()) nxt[i]={p[i].second, 0};
			else nxt[i]=nxt[b];
			nxt[i].second++;
		}
	}
	pair<int, int> get(int x) {
		auto k=lower_bound(p.begin(), p.end(), pair<int, int>(x, 0))-p.begin();
		if (k>=p.size()) return {x, 0};
		return nxt[k];
	}
};

int getmx(int s, int e, vector<myst> &st) {
	int r=0, x=1;
	for (auto &i:st) if (i.p.size()) {
		if (i.p.back().second<=s) {
			auto k=i.get(x);
			x=k.first;
			r+=k.second;
		}
		else {
			for (auto &j:i.p) {
				if (j.second>s) break;
				if (x<=j.first) r++, x=j.second;
			}
			break;
		}
	}
	x=e;
	int fl=0;
	for (auto &i:st) if (i.p.size()&&i.p.back().first>=e) {
		if (!fl) {
			fl=1;
			for (auto &j:i.p) if (x<=j.first) r++, x=j.second;
			continue;
		}
		auto k=i.get(x);
		x=k.first;
		r+=k.second;
	}
	return r;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, k;
	cin>>n>>k;
	vector<pair<int, int>> v(n), s;
	for (auto &i:v) cin>>i.first>>i.second, s.emplace_back(i);
	
	sort(s.begin(), s.end());
	vector<pair<int, int>> w;
	for (auto &i:s) {
		if (w.size()&&w.back().first==i.first) continue;
		while (w.size()&&w.back().second>=i.second) w.pop_back();
		w.emplace_back(i);
	}
	
	vector<myst> st((w.size()+B-1)/B);
	for (int i=0; i<w.size(); i+=B) {
		int e=min(i+B, (int)w.size());
		for (int j=i; j<e; j++) st[i/B].p.emplace_back(w[j]);
		st[i/B].init();
	}

	if (getmx(0, 0, st)<k) {
		cout<<-1;
		return 0;
	}

	set<pair<int, int>> vl;
	auto col = [&](pair<int, int> p) {
		auto k=vl.lower_bound({p.first, 0});
		if (k!=vl.end()&&k->first<p.second) return 0;
		if (k!=vl.begin()&&prev(k)->second>p.first) return 0;
		return 1;
	};

	for (int t=0; k&&t<n; t++) if (col(v[t])&&getmx(v[t].first, v[t].second, st)>=k-1) {
		vl.emplace(v[t]);
		cout<<t+1<<'\n';
		auto [s, e]=v[t];
		for (auto &i:st) if (i.p.size()) {
			int l=i.p[0].first, r=i.p.back().second;
			if (r<=s||e<=l) continue;
			if (s<=l&&r<=e) {
				i.p.clear();
				continue;
			}
			vector<pair<int, int>> pp;
			for (auto &j:i.p) if (j.second<=s||j.first>=e) pp.emplace_back(j);
			swap(pp, i.p);
			i.init();
		}
		k--;
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

event2.cpp: In member function 'void myst::init()':
event2.cpp:14:9: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |    if (b>=p.size()) nxt[i]={p[i].second, 0};
      |        ~^~~~~~~~~~
event2.cpp: In member function 'std::pair<int, int> myst::get(int)':
event2.cpp:21:8: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if (k>=p.size()) return {x, 0};
      |       ~^~~~~~~~~~
event2.cpp: In function 'int main()':
event2.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i=0; i<w.size(); i+=B) {
      |                ~^~~~~~~~~

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