Submission #593077

#	Time	Username	Problem	Language	Result	Execution time	Memory
593077		Zanite	Segments (IZhO18_segments)	C++17	0 / 100	2 ms	468 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.fi, b.se - a.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);

		auto F = saved.begin();
		auto M = saved.end();
		auto L = saved.end() + pending.size();

		for (auto &i : pending) {saved.push_back(i);}
		pending.clear();

		inplace_merge(F, M, L, comp);

		// 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 < saved.size(); i++) {
			left[ptr].push_back(saved[i].fi);
			right[ptr].push_back(saved[i].se);

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

			if (len[st + 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 + 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 = 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);
		}

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

Compilation message (stderr)

segments.cpp: In member function 'void DelayedVector::rebuild()':
segments.cpp:48:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int ptr = 0, i = 0; i < saved.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
segments.cpp:52:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |    if (left[ptr].size() >= sqrtn) {
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~
segments.cpp: In member function 'void DelayedVector::update(int, int)':
segments.cpp:68:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   if (pending.size() > sqrtn) {rebuild();}
      |       ~~~~~~~~~~~~~~~^~~~~~~
segments.cpp: In member function 'int DelayedVector::query(int, int, int)':
segments.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int i = 0; i < left.size(); st += left[i].size(), i++) {
      |                   ~~^~~~~~~~~~~~~
segments.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    assert_WA(st < saved.size());
      |              ~~~^~~~~~~~~~~~~~
segments.cpp:20:26: note: in definition of macro 'assert_WA'
   20 | #define assert_WA(x) if (x) printf("!!!\n")
      |                          ^
segments.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int j = st; j < st + left[i].size(); j++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |  scanf("%d %d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
segments.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |    scanf("%d %d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |    scanf("%d", &id);
      |    ~~~~~^~~~~~~~~~~
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 %d", &a, &b, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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