제출 #930209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930209		NK_	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	943 ms	40576 KiB

Main

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

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
using vi = V<int>;

struct Seg {
	const int ID = 0; int cmb(int a, int b) { return a + b; };
	vi seg, lazy; int N; void init(int n) {
		for(N = 1; N < n; N *= 2); 
		seg.assign(2 * N, 0); lazy.assign(2 * N, -1);
	}

	void pull(int x) { seg[x] = cmb(seg[2*x], seg[2*x+1]); }

	void push(int x, int L, int R) {
		if (lazy[x] != -1) {
			seg[x] = (R-L+1) * lazy[x];
			if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] = lazy[x];
			lazy[x] = -1;
		}
	}

	void upd(int l, int r, int v, int x, int L, int R) {
		push(x, L, R); if (R < l || r < L) return;
		if (l <= L && R <= r) {
			lazy[x] = v; push(x, L, R); return;
		}
		int M = (L + R) / 2;
		upd(l, r, v, 2 * x, L, M);
		upd(l, r, v, 2 * x + 1, M + 1, R);
		pull(x);
	}

	int query(int l, int r, int x, int L, int R) {
		push(x, L, R); if (R < l || r < L) return ID;
		if (l <= L && R <= r) return seg[x];
		int M = (L + R) / 2;
		return cmb(query(l, r, 2 * x, L, M), query(l, r, 2 * x + 1, M + 1, R));
	}

	void upd(int l, int r, int v) { upd(l, r, v, 1, 0, N - 1); }
	int qry(int l, int r) { return query(l, r, 1, 0, N - 1); }
};

const int LG = 19;
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;
	}
	
	Seg st; st.init(M);

	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 && !st.qry(L[bnd], R[bnd])) {
			st.upd(L[bnd], R[bnd], 1);
			bnd++;
		}

		nxt[i][0] = bnd;
		// cout << i << " => " << bnd << endl;
		st.upd(L[i], R[i], 0);
	}

	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);
}

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