Submission #798610

#	Time	Username	Problem	Language	Result	Execution time	Memory
798610		kingfran1907	Segments (IZhO18_segments)	C++14	100 / 100	3242 ms	14728 KiB

segments

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int block = 1500;

int n, t;
int cnt = 0;
vector< int > lef[maxn], rig[maxn];
int L[maxn], R[maxn];
int bio[maxn];
vector< pair<int, int> > v;
int inds[maxn];
int ptr;

bool cmp(int x, int y) {
	return R[x] - L[x] < R[y] - L[y];
}

inline int inter(int ax, int ay, int bx, int by) {
	return min(ay, by) - max(ax, bx) + 1;
}

int main() {
	scanf("%d%d", &n, &t);
	int lastans = 0;
	while (n--) {
		int type;
		scanf("%d", &type);
		if (type == 1) {
			int l, r;
			scanf("%d%d", &l, &r);
			l = l ^ (t * lastans);
			r = r ^ (t * lastans);
			if (l > r) swap(l, r);
			//printf("adding: %d %d\n", l, r);
			
			++cnt;
			v.push_back({cnt, 1});
			L[cnt] = l, R[cnt] = r;
		} else if (type == 2) {
			int x;
			scanf("%d", &x);
			v.push_back({x, -1});
		} else {
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			l = l ^ (t * lastans);
			r = r ^ (t * lastans);
			if (l > r) swap(l, r);
			//printf("query: %d %d\n", l, r);
			
			lastans = 0;
			for (int i = 0; i < ptr; i += block) {
				int tr = i / block;
				int las = min(ptr, i + block) - 1;
				
				/*printf("block: ");
				for (int j = 0; j < block; j++) {
					if (i + j >= inds.size()) break;
					printf("(%d %d) ", L[inds[i + j]], R[inds[i + j]]);
				}
				printf("\n");*/
								
				if (R[inds[las]] - L[inds[las]] + 1 < k) continue;
				if (R[inds[i]] - L[inds[i]] + 1 >= k) {
					lastans += las - i + 1;
					int ind = lower_bound(rig[tr].begin(), rig[tr].end(), l + k - 1) - rig[tr].begin();
					//printf("removing: %d\n", ind);
					lastans -= ind;
					ind = upper_bound(lef[tr].begin(), lef[tr].end(), r - k + 1) - lef[tr].begin();
					lastans -= lef[tr].size() - ind;
					//printf("removing: %d\n", lef[tr].size() - ind);
				} else {
					for (int j = 0; j < block; j++) {
						if (i + j >= ptr) break;
						lastans += (inter(l, r, L[inds[i + j]], R[inds[i + j]]) >= k);
					}
				}
			}
			
			for (auto &iter : v) {
				int ind = iter.X;
				int cost = iter.Y;
				if (inter(l, r, L[ind], R[ind]) >= k) lastans += cost;
			}
			printf("%d\n", lastans);
		}
		
		if (n % block == 0) {
			for (int i = 0; i <= ptr / block; i++) {
				lef[i].clear();
				rig[i].clear();
			}
			
			for (auto &iter : v) {
				bio[iter.X] += iter.Y;
			}
			v.clear();
			
			ptr = 0;
			for (int i = 1; i <= cnt; i++) {
				if (bio[i]) inds[ptr++] = i;
			}
			sort(inds, inds + ptr, cmp);
			
			for (int i = 0; i < ptr; i++) {
				int tr = i / block;
				lef[tr].push_back(L[inds[i]]);
				rig[tr].push_back(R[inds[i]]);
			}
			for (int i = 0; i <= ptr / block; i++) {
				sort(lef[i].begin(), lef[i].end());
				sort(rig[i].begin(), rig[i].end());
			}
		}
	}
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d", &type);
      |   ~~~~~^~~~~~~~~~~~~
segments.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
segments.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |    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