Submission #41729

#	Time	Username	Problem	Language	Result	Execution time	Memory
41729		aome	Segments (IZhO18_segments)	C++14	100 / 100	4373 ms	40960 KiB

segments

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

const int N = 200005;
const int B = 1500;

int n, t, sz, lastans;
int cnt;
int L[N], R[N];
bool del[N];
int sz_add, sz_del;
int buf_add[B];
int buf_del[B];
int sz_l[500], sz_r[500];
int block_l[500][B];
int block_r[500][B];
int sz_go;
pair<int, int> go[N];

void prep() {
	sz_go = 0;
	for (int i = 1; i <= sz; ++i) {
		if (!del[i]) go[sz_go++] = make_pair(R[i] - L[i] + 1, i);
	}
	sort(go, go + sz_go);
	sz_add = sz_del = 0;
	int m = sz_go;
	for (int i = 0; i <= m / B; ++i) sz_l[i] = 0, sz_r[i] = 0;
	for (int i = 0; i < m; ++i) block_l[i / B][sz_l[i / B]++] = L[go[i].second];
	for (int i = 0; i < m; ++i) block_r[i / B][sz_r[i / B]++] = R[go[i].second]; 
	for (int i = 0; i <= m / B; ++i) {
		sort(block_l[i], block_l[i] + sz_l[i]);
		sort(block_r[i], block_r[i] + sz_r[i]);
	}
}

int calc(int id, int l, int r) {
	// count number of commont points betweeen L[id], R[id] and l, r
	if (L[id] > l) return max(0, min(r, R[id]) - L[id] + 1);
	return max(0, min(R[id], r) - l + 1);
}

int calL(int l, int r, int x) {
	// count number of segments from l -> r which has L > x
	int res = 0;
	int bl = l / B, br = r / B;
	if (bl == br) {
		for (int i = l; i <= r; ++i) res += L[go[i].second] > x;
		return res;
	}
	for (int i = bl + 1; i < br; ++i) {
		int tmp = lower_bound(block_l[i], block_l[i] + sz_l[i], x + 1) - block_l[i];
		res += B - tmp;
	}
	for (int i = l; i < (bl + 1) * B; ++i) res += L[go[i].second] > x;
	for (int i = br * B; i <= r; ++i) res += L[go[i].second] > x;
	return res;
}

int calR(int l, int r, int x) {
	// count number of segments from l -> r which has R < x
	int res = 0;
	int bl = l / B, br = r / B;
	if (bl == br) {
		for (int i = l; i <= r; ++i) res += R[go[i].second] < x;
		return res;
	}
	for (int i = bl + 1; i < br; ++i) {
		int tmp = lower_bound(block_r[i], block_r[i] + sz_r[i], x) - block_r[i];
		res += tmp;
	}
	for (int i = l; i < (bl + 1) * B; ++i) res += R[go[i].second] < x;
	for (int i = br * B; i <= r; ++i) res += R[go[i].second] < x;
	return res;
}

int main() {
	scanf("%d %d", &n, &t);
	for (int i = 1; i <= n; ++i) {
		if (i % B == 0) prep();

		int type; scanf("%d", &type);

		if (type == 1) {
			int l, r; scanf("%d %d", &l, &r);
			l = l ^ (1LL * t * lastans);
			r = r ^ (1LL * t * lastans);
			if (l > r) swap(l, r);
			++sz, L[sz] = l, R[sz] = r, buf_add[sz_add++] = sz, cnt++;
		}

		if (type == 2) {
			int x; scanf("%d", &x), buf_del[sz_del++] = x, del[x] = 1, cnt--;
		}

		if (type == 3) {
			int l, r, k; 
			scanf("%d %d %d", &l, &r, &k);
			l = l ^ (1LL * t * lastans);
			r = r ^ (1LL * t * lastans);
			if (l > r) swap(l, r);

			if (r - l + 1 < k) {
				lastans = 0, printf("0\n"); continue;
			} 

			int res = 0;	

			for (int j = 0; j < sz_add; ++j) res += calc(buf_add[j], l, r) < k;
			for (int j = 0; j < sz_del; ++j) res -= calc(buf_del[j], l, r) < k;

			int p = lower_bound(go, go + sz_go, make_pair(k, 0)) - go;

			// number of segments r - l + 1 < k
			res += p;

			// query p -> go.size() - 1 (segments with size >= k)

			// count number of segments L > r - k + 1
			res += calL(p, sz_go - 1, r - k + 1);
			// count number of segments R < l + k - 1
			res += calR(p, sz_go - 1, l + k - 1);

			res = cnt - res, lastans = res;
			printf("%d\n", res);
		}
	}
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:78:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &t);
                        ^
segments.cpp:82:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int type; scanf("%d", &type);
                               ^
segments.cpp:85:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l, r; scanf("%d %d", &l, &r);
                                    ^
segments.cpp:93:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x), buf_del[sz_del++] = x, del[x] = 1, cnt--;
                                                                    ^
segments.cpp:98:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &l, &r, &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