Submission #50904

#	Time	Username	Problem	Language	Result	Execution time	Memory
50904		Nicksechko	Segments (IZhO18_segments)	C++14	100 / 100	2613 ms	172032 KiB

segments

#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;
 
/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const ll INF = 1e10;

const int MAXN = 210000;

const int SQ = 500;
const int MX = SQ * 2;
const int BL = MAXN / SQ + 2;

const int UPD = SQ;

struct seg {
	ll l, r, k;
	int gl, gr, gk;
	int ds;
};

seg arr[MAXN];
int cid;
vector<int> gkk[BL];
vector<int> gll[BL];
vector<int> grr[BL];
ll sgl[BL];
ll sgr[BL];
ll sgk[BL];

int gks[BL];
int gls[BL];
int grs[BL];

int glr[BL][BL];
int glk[BL][BL];
int grl[BL][BL];
int grk[BL][BL];
int gkl[BL][BL];
int gkr[BL][BL];

int n, t;

int bl;

bool cmpl(int a, int b) {
	return arr[a].l > arr[b].l;
}
bool cmpr(int a, int b) {
	return arr[a].r < arr[b].r;
}
bool cmpk(int a, int b) {
	return arr[a].k > arr[b].k;
}

int sum = 0;

void rebuild() {
	int start = clock();
	int cnt = 0;
	vector<int> vv;
	for (int i = 0; i < cid; ++i)
		if (!arr[i].ds)
			++cnt, vv.push_back(i);
	for (int i = 0; i < bl; ++i) {
		gkk[i].clear(), gll[i].clear(), grr[i].clear();
		sgk[i] = sgl[i] = sgr[i] = INF;
		gks[i] = gls[i] = grs[i] = 0;
		for (int j = 0; j < bl; ++j)
			glr[i][j] = glk[i][j] = grl[i][j] = grk[i][j] = gkl[i][j] = gkr[i][j] = 0;
	}
	bl = (cnt + SQ - 1) / SQ;
	for (int i = 0; i < bl; ++i) {
		sgk[i] = sgl[i] = sgr[i] = INF;
	}
	sort(vv.begin(), vv.end(), cmpl);
	for (int i = 0; i < vv.size(); ++i) {
		arr[vv[i]].gl = i / SQ;
	}
	sort(vv.begin(), vv.end(), cmpr);
	for (int i = 0; i < vv.size(); ++i) {
		arr[vv[i]].gr = i / SQ;
	}
	sort(vv.begin(), vv.end(), cmpk);
	for (int i = 0; i < vv.size(); ++i) {
		arr[vv[i]].gk = i / SQ;
	}
	for (int i = 0; i < cid; ++i) {
		if (arr[i].ds)
			continue;
		gll[arr[i].gl].push_back(i);
		grr[arr[i].gr].push_back(i);
		gkk[arr[i].gk].push_back(i);
		++gls[arr[i].gl];
		++grs[arr[i].gr];
		++gks[arr[i].gk];
		sgl[arr[i].gl] = min(sgl[arr[i].gl], -arr[i].l);
		sgr[arr[i].gr] = min(sgr[arr[i].gr], arr[i].r);
		sgk[arr[i].gk] = min(sgk[arr[i].gk], -arr[i].k);
		int a = arr[i].gl;
		int b = arr[i].gr;
		int c = arr[i].gk;
		++glr[a][b], ++glk[a][c], ++grl[b][a], ++grk[b][c], ++gkl[c][a], ++gkr[c][b];
	}

	for (int i = 0; i < bl; ++i) {
		for (int j = 0; j < bl - 1; ++j) {
			glr[i][j + 1] += glr[i][j];
			glk[i][j + 1] += glk[i][j];
			grl[i][j + 1] += grl[i][j];
			grk[i][j + 1] += grk[i][j];
			gkl[i][j + 1] += gkl[i][j];
			gkr[i][j + 1] += gkr[i][j];
		}
	}

	sgk[0] = sgl[0] = sgr[0] = -INF;
	bl = max(1, bl);
	sum += clock() - start;
}

int main() {
	scanf("%d%d", &n, &t);
	int curans = 0;
	int fll = 1;
	for (int i = 0; i < n; ++i) {
		if (fll) {
			fll = 0;
			rebuild();
		}
		int tp;
		scanf("%d", &tp);
		if (tp == 1) {
			ll l, r;
			scanf("%lld%lld", &l, &r);
			l = l ^ (t * curans);
			r = r ^ (t * curans);
			if (l > r)
				swap(l, r);
			++r;
			ll k = r - l;
			arr[cid].l = l;
			arr[cid].r = r;
			arr[cid].k = r - l;
			int a = 0, b = 0, c = 0;
			while (a < bl && sgl[a] <= -l)
				++a;
			while (b < bl && sgr[b] <= r)
				++b;
			while (c < bl && sgk[c] <= -k)
				++c;
			a = max(0, a - 1), b = max(0, b - 1), c = max(0, c - 1);
			arr[cid].gl = a;
			arr[cid].gr = b;
			arr[cid].gk = c;
			++gls[a];
			++grs[b];
			++gks[c];
			gll[a].push_back(cid);
			grr[b].push_back(cid);
			gkk[c].push_back(cid);
			for (int i = b; i < bl; ++i)
				++glr[a][i];
			for (int i = c; i < bl; ++i)
				++glk[a][i];
			for (int i = a; i < bl; ++i)
				++grl[b][i];
			for (int i = c; i < bl; ++i)
				++grk[b][i];
			for (int i = a; i < bl; ++i)
				++gkl[c][i];
			for (int i = b; i < bl; ++i)
				++gkr[c][i];
			++cid;
		}
		else if (tp == 2) {
			int id;
			scanf("%d", &id);
			--id;
			arr[id].ds = 1;
			int a = arr[id].gl;
			int b = arr[id].gr;
			int c = arr[id].gk;
			--gls[a];
			--grs[b];
			--gks[c];
			for (int i = b; i < bl; ++i)
				--glr[a][i];
			for (int i = c; i < bl; ++i)
				--glk[a][i];
			for (int i = a; i < bl; ++i)
				--grl[b][i];
			for (int i = c; i < bl; ++i)
				--grk[b][i];
			for (int i = a; i < bl; ++i)
				--gkl[c][i];
			for (int i = b; i < bl; ++i)
				--gkr[c][i];
		}
		else {
			ll x, y, k;
			scanf("%lld%lld%lld", &x, &y, &k);
			x = (x ^ (t * curans));
			y = (y ^ (t * curans));
			if (x > y)
				swap(x, y);
			++y;
			if (y - x < k) {
				curans = 0;
				printf("0\n");
				continue;
			}
			int a = 0, b = 0, c = 0;
			int ans = 0;
			while (c < bl && sgk[c] <= -k)
				++c;
			while (b < bl && sgr[b] < x + k)
				++b;
			while (a < bl && sgl[a] < k - y)
				++a;
			--a;
			--b;
			--c;
			for (int i = 0; i < c; ++i) {
				ans += gks[i];
				if (a > 0)
					ans -= gkl[i][a - 1];
				if (b > 0)
					ans -= gkr[i][b - 1];
			}
			if (gkk[c].size() > MX)
				fll = 1;
			if (gll[a].size() > MX)
				fll = 1;
			if (grr[b].size() > MX)
				fll = 1;
			for (int id: gkk[c]) {
				if (arr[id].ds || arr[id].r < x + k || arr[id].l > y - k || arr[id].k < k)
					continue;
				++ans;
			}
			for (int id: gll[a]) {
				if (!arr[id].ds && arr[id].l > y - k && arr[id].gk < c)
					--ans;
			}
			if (b < bl) {
				for (int id: grr[b]) {
					if (!arr[id].ds && arr[id].r < x + k && arr[id].gk < c)
						--ans;
				}
			}
			printf("%d\n", ans);
			curans = ans;
		}
	}
	//cerr << ld(sum) / CLOCKS_PER_SEC << "\n";
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void rebuild()':
segments.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
segments.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
segments.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); ++i) {
                  ~~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &t);
  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
   ~~~~~^~~~~~~~~~~
segments.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:194:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &id);
    ~~~~~^~~~~~~~~~~
segments.cpp:218:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld", &x, &y, &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