Submission #580213

#	Time	Username	Problem	Language	Result	Execution time	Memory
580213		penguinhacker	Event Hopping (BOI22_events)	C++14	25 / 100	1596 ms	10036 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, ls[2*mxN], rs[2*mxN], ans[mxN];
ar<int, 2> segs[mxN];
vector<int> d;
vector<ar<int, 3>> qry[2*mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i) {
		cin >> segs[i][0] >> segs[i][1];
		d.push_back(segs[i][0]);
		d.push_back(segs[i][1]);
	}
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	memset(ls, -1, sizeof(ls));
	for (int i=0; i<n; ++i) {
		segs[i][0]=lower_bound(d.begin(), d.end(), segs[i][0])-d.begin();
		segs[i][1]=lower_bound(d.begin(), d.end(), segs[i][1])-d.begin();
		//cout << "seg  " <<  segs[i][0] << " " << segs[i][1] << endl;
		if (ls[segs[i][1]]==-1||segs[i][0]<ls[segs[i][1]])
			ls[segs[i][1]]=segs[i][0];
	}
	for (int i=0; i<q; ++i) {
		int a, b;
		cin >> a >> b, --a, --b;
		ans[i]=-1;
		if (segs[a][1]<segs[b][1])
			qry[segs[b][1]].push_back({segs[a][1], segs[b][0], i});
		if (segs[a][1]==segs[b][1])
			ans[i]=a!=b;
	}
	iota(rs, rs+d.size(), 0);
	for (int i=0; i<d.size(); ++i) {
		if (ls[i]!=-1)
			for (int j=ls[i]; j<=i; ++j)
				rs[j]=i;
		//for (int j=0; j<=i; ++j)
		//	cout << rs[j] << " ";
		//cout << endl;
		for (auto [s, bound, ind] : qry[i]) {
			int cur=0;
			while(rs[s]<i&&rs[s]!=s)
				++cur, s=rs[s];
			if (rs[s]!=i)
				continue;
			++cur;
			cur+=s<bound;
			ans[ind]=cur;
		}
	}
	for (int i=0; i<q; ++i) {
		if (ans[i]==-1)
			cout << "impossible\n";
		else
			cout << ans[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
events.cpp:49:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   for (auto [s, bound, ind] : qry[i]) {
      |             ^

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30