Submission #572540

#	Time	Username	Problem	Language	Result	Execution time	Memory
572540		vovamr	Segments (IZhO18_segments)	C++17	7 / 100	5097 ms	46280 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 b = 520;
map<int,pair<oset<int>,oset<int>>> blocks;
map<int,pair<oset<int>,oset<int>>> st;
inline void add(int l, int r) {
	int pos = r / b;
	blocks[pos].fi.insert(l);
	blocks[pos].se.insert(-(r - l + 1));
	st[r].fi.insert(l);
	st[r].se.insert(-(r - l + 1));
}
inline void del(int l, int r) {
	int pos = r / b;
	blocks[pos].fi.erase(blocks[pos].fi.lower_bound(l - 1));
	blocks[pos].se.erase(blocks[pos].se.lower_bound(-(r - l + 1) - 1));
	if (!sz(blocks[pos].fi)) blocks.erase(pos);
	st[r].fi.erase(st[r].fi.lower_bound(l - 1));
	st[r].se.erase(st[r].se.lower_bound(-(r - l + 1) - 1));
	if (!sz(st[r].fi)) st.erase(r);
}

inline int answer(int l, int r, int k) {
	if (r - l + 1 < k) return 0;
	int ans = 0;
	int ps = (r + 1) / b;
	auto it = blocks.upper_bound(ps);
	while (it != blocks.end()) { ans += it->se.fi.order_of_key(r - k + 2); ++it; }
	auto it1 = st.lower_bound(r + 1);
	while (it1 != st.end() && it1->fi < (ps + 1) * b) { ans += it1->se.fi.order_of_key(r - k + 2); ++it1; }

	{
		l = l + k - 1;
		int lb = l / b, rb = r / b;
		if (lb == rb) {
			it = st.lower_bound(l);
			while (it != st.end() && it->fi <= r) {
				ans += it->se.se.order_of_key(-k + 1);
				++it;
			}
		}
		else {
			it = blocks.lower_bound(lb + 1);
			while (it != blocks.end() && it->fi <= rb - 1) {
				ans += it->se.se.order_of_key(-k + 1);
				++it;
			}
			it = st.lower_bound(l);
			while (it != st.end() && it->fi < (lb + 1) * b) {
				ans += it->se.se.order_of_key(-k + 1);
				++it;
			}
			it = st.lower_bound(rb * b);
			while (it != st.end() && it->fi <= r) {
				ans += it->se.se.order_of_key(-k + 1);
				++it;
			}
		}
	}
	return ans;
}

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

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