Submission #94514

#	Time	Username	Problem	Language	Result	Execution time	Memory
94514		szawinis	Segments (IZhO18_segments)	C++17	75 / 100	5024 ms	38668 KiB

segments

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5+1, MAGIC = 1800;

class TaskD {

	int n, T, id[N], last[N], blk[N];
	bool valid[N];
	pair<int,int> segs[N];
	vector<pair<int,int> > fl, fr;
	vector<vector<int> > tl, tr;

	int get_r(int l, int r, int targ_r) {
		int ret = 0;
		for(l += fr.size(), r += fr.size() + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				auto it = lower_bound(tr[l].begin(), tr[l].end(), targ_r);
				ret += it - tr[l].begin();
//				cout << "get_r " << it - tr[l].begin() << ' ' << *(--it) << endl;
//				for(int x: tr[l]) cout << x << ' ';
//				cout << endl;
				++l;
			}
			if(r & 1) {
				--r;
				auto it = lower_bound(tr[r].begin(), tr[r].end(), targ_r);
				ret += it - tr[r].begin();
//				cout << "get_r " << it - tr[r].begin() << ' ' << *(--it) << endl;
//				for(int x: tr[r]) cout << x << ' ';
//				cout << endl;
			}
		}
		return ret;
	}

	int get_l(int l, int r, int targ_l) {
		int ret = 0;
		for(l += fl.size(), r += fl.size() + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) {
				auto it = upper_bound(tl[l].begin(), tl[l].end(), targ_l);
				ret += tl[l].end() - it;
				++l;
			}
			if(r & 1) {
				--r;
				auto it = upper_bound(tl[r].begin(), tl[r].end(), targ_l);
				ret += tl[r].end() - it;
			}
		}
		return ret;
	}

	void build() {
		tl.clear();
		tr.clear();
		tl.resize(2 * fl.size());
		tr.resize(2 * fr.size());
		sort(fl.begin(), fl.end());
		sort(fr.begin(), fr.end());
		for(int i = 0; i < fl.size(); i++) tl[fl.size() + i] = {fl[i].second};
		for(int i = 0; i < fr.size(); i++) tr[fr.size() + i] = {fr[i].second};
		for(int i = fl.size()-1; i >= 1; i--) {
			merge(tl[i << 1].begin(), tl[i << 1].end(), tl[i << 1 | 1].begin(), tl[i << 1 | 1].end(),
			      back_inserter(tl[i]));
//			cout << i << ' ';
//			for(int x: tl[i]) cout << x << ' ';
//			cout << endl;
		}
		for(int i = fr.size()-1; i >= 1; i--) {
			merge(tr[i << 1].begin(), tr[i << 1].end(), tr[i << 1 | 1].begin(), tr[i << 1 | 1].end(),
			      back_inserter(tr[i]));
		}
	}

public:
	void solve(istream &cin, ostream &cout) {
		cin >> n >> T;
		int lastans = 0, tick = 0, alive = 0;
		for(int i = 0; i < n; i++) {
			segs[i] = {-1, -1};
			blk[i] = i / MAGIC;
		}
		for(int i = 0, inst; i < n; i++) {
			if(i % MAGIC == 0) {
				fl.clear();
				fr.clear();
				for(int j = 0; j < i; j++) {
					if(!valid[id[j]]) continue;
					int len = segs[id[j]].second - segs[id[j]].first + 1;
					fl.emplace_back(len, segs[id[j]].first);
					fr.emplace_back(len, segs[id[j]].second);
				}
				build();
			}
			cin >> inst;
			if(inst == 1) {
				int l, r;
				cin >> l >> r;
				l ^= T * lastans;
				r ^= T * lastans;
				if(l > r) swap(l, r);
				id[i] = ++tick;
				valid[id[i]] = true;
				last[id[i]] = i;
				segs[id[i]] = {l, r};
				++alive;
			} else if(inst == 2) {
				int x;
				cin >> x;
				id[i] = x;
				valid[id[i]] = false;
				--alive;
			} else {
				int l, r, k;
				cin >> l >> r >> k;
				l ^= T * lastans;
				r ^= T * lastans;
				if(l > r) swap(l, r);
				lastans = 0;
				if(r-l+1 < k) {
					cout << lastans << '\n';
					continue;
				}
				// outside block -> three cases
				int idx = lower_bound(fl.begin(), fl.end(), make_pair(k, 0)) - fl.begin();
				lastans += idx; // len < k
				lastans += get_l(idx, fl.size() - 1, r - k + 1); // l[j] > r[i] - k[i] + 1 and len >= k
				lastans += get_r(idx, fr.size() - 1, l + k - 1); // r[j] < l[i] + k[i] - 1 and len >= k
				// within same block
				for(int j = i-1; j >= 0 && blk[j] == blk[i]; j--) {
					if(valid[id[j]]) {
						lastans += min(segs[id[j]].second, r) - max(segs[id[j]].first, l) + 1 < k;
					} else if(segs[id[j]].first != -1 && blk[last[id[j]]] < blk[i]) {
						lastans -= min(segs[id[j]].second, r) - max(segs[id[j]].first, l) + 1 < k;
					}
				}
				lastans = alive - lastans;
				cout << lastans << '\n';
			}
		}
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
	    TaskD *obj = new TaskD();
		obj->solve(in, out);
		delete obj;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message (stderr)

segments.cpp: In member function 'void TaskD::build()':
segments.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < fl.size(); i++) tl[fl.size() + i] = {fl[i].second};
                  ~~^~~~~~~~~~~
segments.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < fr.size(); i++) tr[fr.size() + i] = {fr[i].second};
                  ~~^~~~~~~~~~~

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