Submission #580223

#	Time	Username	Problem	Language	Result	Execution time	Memory
580223		penguinhacker	Event Hopping (BOI22_events)	C++17	10 / 100	111 ms	14672 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];

struct ft {
	int ft[2*mxN+1];
	void upd(int i, int x) {
		for (++i; i<=2*n; i+=i&-i)
			ft[i]+=x;
	}
	int qry(int i) {
		int r=0;
		for (++i; i; i-=i&-i)
			r+=ft[i];
		return r;
	}
} bad, distinct;

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);
	vector<int> ends, bads, end_val;
	for (int i=0; i<d.size(); ++i) {
		distinct.upd(i, 1);
		if (ls[i]!=-1) {
			int last;
			while(ends.size()&&ends.back()>=ls[i]) {
				distinct.upd(ends.back(), -1);
				ends.pop_back();
				last=end_val.back();
				end_val.pop_back();
			}
			if ((ends.empty()&&ls[i])||ends.size()&&ends.back()<ls[i]-1) {
				ends.push_back(ls[i]-1);
				distinct.upd(ls[i]-1, 1);
				end_val.push_back(last);
			}
			while(bads.size()&&ls[i]<=bads.back()) {
				bad.upd(bads.back(), -1);
				bads.pop_back();
			}
		}
		/*cout << i << ": ";
		for (int j : end_val)
			cout << j << " ";
		cout << endl;*/
		for (auto [s, bound, ind] : qry[i]) {
			if (bad.qry(i-1)-bad.qry(s-1))
				continue;
			assert(ls[i]<i);
			int cur=distinct.qry(i-1)-distinct.qry(s-1);
			int pos=cur?end_val.back():s;
			//cout << cur << " " << pos << " " << end_val.back() << endl;
			ans[ind]=cur+1+(pos<bound);
		}
		bad.upd(i, 1);
		ends.push_back(i);
		end_val.push_back(i);
		bads.push_back(i);
	}
	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:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
events.cpp:67:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   67 |    if ((ends.empty()&&ls[i])||ends.size()&&ends.back()<ls[i]-1) {
      |                               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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