Submission #572541

#	Time	Username	Problem	Language	Result	Execution time	Memory
572541		vovamr	Segments (IZhO18_segments)	C++17	0 / 100	47 ms	65536 KiB

segments

#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_equal<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 = 1e5 + 10;
struct iseg {
	int w = 0;
	struct node { int l, r; oset<int> st; } t[110 * N];
	inline int nd() { int v = w++; t[v].l = t[v].r = -1; return v; }
	const int L = 0, R = 2e9 + 10;
	inline void upd(int v, int vl, int vr, int pos, int val) {
		t[v].st.insert(val);
		if (vl == vr) return;
		int m = vl + vr >> 1;
		if (pos <= m) {
			if (!~t[v].l) t[v].l = nd();
			upd(t[v].l, vl, m, pos, val);
		}
		else {
			if (!~t[v].r) t[v].r = nd();
			upd(t[v].r, m + 1, vr, pos, val);
		}
	}
	inline void upd1(int v, int vl, int vr, int pos, int val) {
		t[v].st.erase(t[v].st.lower_bound(val - 1));
		if (vl == vr) return;
		int m = vl + vr >> 1;
		if (pos <= m) upd1(t[v].l, vl, m, pos, val);
		else upd1(t[v].r, m + 1, vr, pos, val);
	}
	inline int get(int v, int vl, int vr, int l, int r, int x) {
		if (!~v) return 0;
		else if (vl == l && vr == r) return t[v].st.order_of_key(x + 1);
		int m = vl + vr >> 1;
		if (r <= m) return get(t[v].l, vl, m, l, r, x);
		else if (l > m) return get(t[v].r, m + 1, vr, l, r, x);
		else return get(t[v].l, vl, m, l, m, x) + get(t[v].r, m + 1, vr, m + 1, r, x);
	}
	inline void add(int x, int y) { upd(0, L, R, x, y); }
	inline void del(int x, int y) { upd1(0, L, R, x, y); }
	inline int get(int l, int r, int x) { if (l > r){return 0;} return get(0, L, R, l, r, x); }
	iseg() { nd(); }
};

const int hui = 2e9 + 10;

iseg s1, s2;
inline void add(int l, int r) { s1.add(r, l), s2.add(r, -(r - l + 1)); }
inline void del(int l, int r) { s1.del(r, l); s2.del(r, -(r - l + 1)); }
inline int answer(int l, int r, int k) {
	if (r - l + 1 < k) return 0;
	int res = 0;
	res += s1.get(r + 1, hui, r - k + 1);
	res += s2.get(l + k - 1, r, -k);
	return res;
}

inline void solve() {
	int n, t;
	cin >> n >> t;

	int lid = 0;
	ve<pii> segs(n);

	int lst = 0;
	while (n--) {
		int e;
		cin >> e;
		if (e == 1) {
			int l, r;
			cin >> l >> r;
			l ^= (t * lst);
			r ^= (t * lst);
			if (l > r) swap(l, r);
			segs[lid++] = {l, r};
			add(l, r);
		}
		else if (e == 2) {
			int id;
			cin >> id, --id;
			del(segs[id].fi, segs[id].se);
		}
		else {
			int l, r, k;
			cin >> l >> r >> k;
			l ^= (t * lst);
			r ^= (t * lst);
			if (l > r) swap(l, r);
			lst = answer(l, r, k);
			cout << lst << '\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)

segments.cpp: In member function 'void iseg::upd(int, int, int, int, int)':
segments.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int m = vl + vr >> 1;
      |           ~~~^~~~
segments.cpp: In member function 'void iseg::upd1(int, int, int, int, int)':
segments.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int m = vl + vr >> 1;
      |           ~~~^~~~
segments.cpp: In member function 'int iseg::get(int, int, int, int, int, int)':
segments.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int m = vl + vr >> 1;
      |           ~~~^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25