Submission #930343

#	Time	Username	Problem	Language	Result	Execution time	Memory
930343		NK_	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	634 ms	39112 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair

template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;

const int LG = 18;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	vi L(N), R(N); for(int i = 0; i < N; i++) cin >> L[i] >> R[i];

	int M = -1;
	{
		map<int, int> mp; int cur = 0;
		for(auto& x : L) mp[x]++; 
		for(auto& x : R) mp[x]++;
		for(auto& x : mp) x.second = cur++;
		for(auto& x : L) x = mp[x];
		for(auto& x : R) x = mp[x];
		M = cur;
	}
	vpi A(N); for(int i = 0; i < N; i++) A[i] = mp(L[i], R[i]);
	
	set<pi> S;

	auto add = [&](pi x) {

		auto it = S.lower_bound(x);

		if (it != end(S)) {
			pi y = *it;
			if (x.s >= y.f) return false;
		}

		if (it != begin(S)) {
			pi y = *prev(it);
			if (y.s >= x.f) return false;
		}	

		S.insert(x);
		return true;
	};

	V<vi> nxt(N + 1, vi(LG, N)); int bnd = 0;
	for(int i = 0; i < N; i++) {
		// cout << i << " ==> " << L[i] << " " << R[i] << endl;
		while(bnd < N && add(A[bnd])) bnd++;

		nxt[i][0] = bnd;
		// cout << i << " => " << bnd << endl;
		S.erase(A[i]);
	}

	for(int x = N - 1; x >= 0; x--) {
		for(int i = 1; i < LG; i++) nxt[x][i] = nxt[nxt[x][i-1]][i-1];
	}

	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int l, r; cin >> l >> r; --l, --r;

		int ans = 0;
		for(int i = LG - 1; i >= 0; i--) {
			if (nxt[l][i] <= r) { ans += (1 << i); l = nxt[l][i]; }
		}

		cout << ans + 1 << nl;
	}



	exit(0-0);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:6: warning: variable 'M' set but not used [-Wunused-but-set-variable]
   24 |  int M = -1;
      |      ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50