Submission #593098

#	Time	Username	Problem	Language	Result	Execution time	Memory
593098		Zanite	Segments (IZhO18_segments)	C++17	100 / 100	1888 ms	17600 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();}

#define assert_WA(x) if (!(x)) printf("!!!\n")

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++) {
			assert_WA(st < (int)saved.size());
			assert_WA(st + (int)left[i].size() - 1 < (int)saved.size());

			if (len[st + (int)left[i].size() - 1] >= k) {
				ans += findLess(left[i], r - (k-1) + 1);
				//cout << ans << '\n';
				ans -= findLess(right[i], l + (k-1));
				//cout << l + (k-1) << ' ' << ans << '\n';

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

	void print() {
		printf("Pending: ");
		for (auto &[l, r] : pending) {printf("[%d, %d] ", l, r);}
		printf("\n");

		printf("Saved: ");
		for (auto &[l, r] : saved) {printf("[%d, %d] ", l, r);}
		printf("\n");

		printf("Left: ");
		for (auto &i : left) {
			printf("[ ");
			for (auto &j : i) {printf("%d ", j);}
			printf("] ");
		}
		printf("\n");

		printf("Right: ");
		for (auto &i : right) {
			printf("[ ");
			for (auto &j : i) {printf("%d ", j);}
			printf("] ");
		}
		printf("\n\n");
	}
};

int main() {
	scanf("%d %d", &n, &t);
	sqrtn = 1000;//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);

			//cerr << i << ' ' << a << ' ' << b << '\n';

		} else if (typ == 2) {
			scanf("%d", &id);
			assert(id < segments.size());

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

			//cerr << i << ' ' << id << '\n';

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

			//cerr << i << ' ' << a << ' ' << b << ' ' << k << '\n';
		}

		//All.print();
		//Deleted.print();
	}
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from segments.cpp:3:
segments.cpp: In function 'int main()':
segments.cpp:168:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |    assert(id < segments.size());
      |           ~~~^~~~~~~~~~~~~~~~~
segments.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |  scanf("%d %d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
segments.cpp:156:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |    scanf("%d %d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:167:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |    scanf("%d", &id);
      |    ~~~~~^~~~~~~~~~~
segments.cpp:175:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |    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