Submission #593179

#	Time	Username	Problem	Language	Result	Execution time	Memory
593179		Zanite	Segments (IZhO18_segments)	C++17	100 / 100	3840 ms	16008 KiB

segments

// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

using pii	= pair<int, int>;

#define fi	first
#define se	second

int n, t, lastans;
vector<pii> segments(1);

int sqrtn;

inline const bool comp(const pii &a,const pii &b) {return ((a.se - a.fi) > (b.se - b.fi));}
inline int intersect(pii a, pii b) {return max(0, min(a.se, b.se) - max(a.fi, b.fi) + 1);}
inline int findLess(vector<int> &v, int x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}

struct DelayedVector {
	vector<pii> pending, saved;
	vector<int> len;
	vector<vector<int>> left, right;

	DelayedVector() {}
	
	void rebuild() {
		sort(pending.begin(), pending.end(), comp);

		vector<pii> temp;
		int i = 0, j = 0;
		for (; i < (int)pending.size() && j < (int)saved.size(); ) {
			if (comp(pending[i], saved[j])) {
				temp.push_back(pending[i]);
				i++;
			} else {
				temp.push_back(saved[j]);
				j++;
			}
		}
		for (; i < (int)pending.size(); i++) temp.push_back(pending[i]);
		for (; j < (int)saved.size(); j++) temp.push_back(saved[j]);

		pending.clear();
		saved = temp;

		// recompute lengths
		len.clear();
		for (auto &[l, r] : saved) {len.push_back(r - l + 1);}

		// recompute blocks
		left.clear(); right.clear();
		left.push_back({}); right.push_back({});
		for (int ptr = 0, i = 0; i < (int)saved.size(); i++) {
			left[ptr].push_back(saved[i].fi);
			right[ptr].push_back(saved[i].se);

			if ((int)left[ptr].size() >= sqrtn) {
				ptr++;
				left.push_back({}); right.push_back({});
			}
		}
		if (left.back().empty()) {left.pop_back();}
		if (right.back().empty()) {right.pop_back();}

		for (auto &i : left) {sort(i.begin(), i.end());}
		for (auto &i : right) {sort(i.begin(), i.end());}

		
	}

	void update(int l, int r) {
		pending.push_back({l, r});

		// rebuild the sqrt decomposition
		if ((int)pending.size() > sqrtn) {rebuild();}
	}

	int query(int k, int l, int r) {
		// a segment [x, y] does not have at least k points in common with [l, r] if
		// x > (r - (k - 1)) || y < (l + (k - 1))

		if (k > (r - l + 1)) return 0;

		int ans = 0;
		pii segment = {l, r};

		for (auto &p : pending) {
			if (intersect(segment, p) >= k) {ans++;}
		}

		int st = 0;
		for (int i = 0; i < (int)left.size(); st += (int)left[i].size(), i++) {
			if (len[st + (int)left[i].size() - 1] >= k) {
				ans += findLess(left[i], r - (k-1) + 1);
				ans -= findLess(right[i], l + (k-1));

			} else if (len[st] >= k) {
				for (int j = st; j < st + (int)left[i].size(); j++) {
					if (intersect(segment, saved[j]) >= k) {ans++;}
				}

			} else break;
		}

		return ans;
	}
};

int main() {
	scanf("%d %d", &n, &t);
	sqrtn = sqrt(n);
	DelayedVector All, Deleted;

	for (int typ, a, b, k, id, i = 1; i <= n; i++) {
		scanf("%d", &typ);

		if (typ == 1) {
			scanf("%d %d", &a, &b);
			a ^= (t * lastans);
			b ^= (t * lastans);
			if (a > b) {swap(a, b);}

			segments.push_back({a, b});
			All.update(a, b);

		} else if (typ == 2) {
			scanf("%d", &id);

			Deleted.update(segments[id].fi, segments[id].se);

		} else {
			scanf("%d %d %d", &a, &b, &k);
			a ^= (t * lastans);
			b ^= (t * lastans);
			if (a > b) {swap(a, b);}

			lastans = All.query(k, a, b) - Deleted.query(k, a, b);
			printf("%d\n", lastans);
		}
	}
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  scanf("%d %d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
segments.cpp:119:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |    scanf("%d %d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:128:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |    scanf("%d", &id);
      |    ~~~~~^~~~~~~~~~~
segments.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |    scanf("%d %d %d", &a, &b, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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