Submission #626795

#	Time	Username	Problem	Language	Result	Execution time	Memory
626795		vovamr	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	697 ms	34248 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 4e5 + 10;
int t[4 * N], p[4 * N];
inline void mg(int v) { t[v] = max(t[2 * v + 1], t[2 * v + 2]); }
inline void push(int v) {
	if (!p[v]) return;
	p[2 * v + 1] += p[v]; t[2 * v + 1] += p[v];
	p[2 * v + 2] += p[v]; t[2 * v + 2] += p[v];
	p[v] = 0;
}
inline void upd(int v, int vl, int vr, int l, int r, int x) {
	if (l > r) return;
	else if (vl == l && vr == r) {
		t[v] += x, p[v] += x;
		return;
	}
	push(v);
	int m = vl + vr >> 1;
	upd(2 * v + 1, vl, m, l, min(r, m), x);
	upd(2 * v + 2, m + 1, vr, max(l, m + 1), r, x);
	mg(v);
}
inline int get(int v, int vl, int vr, int l, int r) {
//	cout << v << " [" << vl << ", " << vr << "] and seg [" << l <<  ", " << r << "]" << '\n';
	if (l > r) return -iinf;
	else if (vl == l && vr == r) return t[v];
	push(v);
	int m = vl + vr >> 1;
	return max(get(2*v+1,vl,m,l,min(r,m)),get(2*v+2,m+1,vr,max(l,m+1),r));
}

const int lg = 19;
const int M = 2e5 + 10;

int up[M][lg];

inline void solve() {
	int n;
	cin >> n;
	ve<pii> a(n);
	for (auto &[l, r] : a) cin >> l >> r;

	ve<int> al;
	for (auto &[l, r] : a) al.pb(l), al.pb(r);
	sort(all(al)), al.erase(unique(all(al)), al.end());
	for (auto &[l, r] : a) {
		l = lower_bound(all(al), l) - al.begin();
		r = lower_bound(all(al), r) - al.begin();
	}
	int m = sz(al);

	ve<int> border(n);
	for (int l = 0, r = -1; l < n; ++l) {
		auto &[le, re] = a[l];
//		cout << get(0, 0, m - 1, le, re) << " !" << '\n';
		while (r + 1 < n) {
			auto &[lf, rg] = a[r + 1];
			if (get(0, 0, m - 1, lf, rg) > 0) break;
			upd(0, 0, m - 1, lf, rg, +1);
			++r;
		}
		border[l] = r;
		upd(0, 0, m - 1, le, re, -1);
	}

//	for (int i = 0; i < n; ++i) {
//		cout << i + 1 << ": " << border[i] + 1 << '\n';
//	}

	for (int k = 0; k < lg; ++k) up[n][k] = up[n + 1][k] = n;

	for (int l = 0; l < n; ++l) up[l][0] = border[l];
	for (int k = 1; k < lg; ++k) {
		for (int l = 0; l < n; ++l) {
			up[l][k] = up[up[l][k - 1] + 1][k - 1];
		}
	}


	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r, --l, --r;

		int ans = 0;
		for (int i = lg - 1; ~i; --i) {
			if (up[l][i] < r) {
				ans += (1 << i);
				l = up[l][i] + 1;
			}
		}
		cout << ans + 1 << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int m = vl + vr >> 1;
      |          ~~~^~~~
Main.cpp: In function 'int get(int, int, int, int, int)':
Main.cpp:49:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int m = vl + vr >> 1;
      |          ~~~^~~~

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