Submission #340154

#	Time	Username	Problem	Language	Result	Execution time	Memory
340154		GioChkhaidze	Segments (IZhO18_segments)	C++14	100 / 100	2285 ms	11524 KiB

segments

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int N = 2e5 + 5;
const int Sq = 1100;

int A[N], B[N], C[N];
int n, u, t, bl, lastans;
int sq = 1200;

struct st { int x; };

bool operator<(const st& a,const st& b) { 
	return C[a.x] < C[b.x]; 
}

struct {
	vector < st > u, c, ol;
	vector < int > L[N / Sq], R[N / Sq]; 

	void insert(st id) {
		u.pb(id);
		if (u.size() == sq) {
			vector < st > c;
			c.reserve(u.size() + ol.size());
			sort(u.begin(), u.end());
			merge(u.begin(), u.end(), ol.begin(), ol.end(), back_inserter(c));
			ol.swap(c); u.clear();
			
			for (int bl = 0; bl*sq < ol.size(); ++bl) {
				L[bl].clear(), R[bl].clear();
			}
			
			for (int i = 0; i < ol.size(); ++i) {
				bl = i / sq;
				L[bl].pb(A[ol[i].x]);
				R[bl].pb(B[ol[i].x]);
			}
			
			for (int bl = 0; bl*sq < ol.size(); ++bl) {
				sort(L[bl].begin(),L[bl].end());
				sort(R[bl].begin(),R[bl].end());
			}
		}
	}
	
	int solve(int l, int r, int k) {
		if (r - l + 1 < k) return 0;
		int ans = 0, s, f, S, F, i;
		for (i = 0; i < u.size(); ++i) 
			if (min(r, B[u[i].x]) - max(l, A[u[i].x]) + 1 >= k) 
				++ans;
		
		for (s = 0; s < ol.size(); s += sq) {
			f = min(s + sq - 1, (int)ol.size() - 1);

			if (C[ol[s].x] >= k) {
				bl = f / sq;
				ans += f - s + 1;
				ans -= L[bl].end() - upper_bound(L[bl].begin(), L[bl].end(), r - k + 1); 
				ans -= lower_bound(R[bl].begin(), R[bl].end(), l + k - 1) - R[bl].begin();
			}
				else
			if (C[ol[f].x] >= k) {
				for (i = s; i <= f; ++i) 
					if (min(r, B[ol[i].x]) - max(l, A[ol[i].x]) + 1 >= k)
						 ++ans;
			}
		}

		return ans;
	}
	
} rcur, cur;

int G(int &x, int &y) {
	x = (x ^ (t * lastans));
	y = (y ^ (t * lastans));
	if (x > y) swap(x, y);
	return y - x + 1;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> t;
	st b;
	int ty, id, l, r, k;
	for (int i = 0; i < n; ++i) {
		cin >> ty;
		if (ty == 1) { 
			cin >> A[u] >> B[u]; 
			C[u] = G(A[u], B[u]); b.x = u;
			cur.insert(b), ++u;
		}
			else
		if (ty == 2) { 
			cin >> id; --id; b.x = id;
			rcur.insert(b);
		}
			else
		if (ty == 3) { 
			cin >> l >> r >> k; G(l, r);
			lastans = cur.solve(l, r, k) - rcur.solve(l, r, k);
			cout << lastans << "\n";
		}
	}
}

Compilation message (stderr)

segments.cpp: In member function 'void<unnamed struct>::insert(st)':
segments.cpp:26:16: warning: comparison of integer expressions of different signedness: 'std::vector<st>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   if (u.size() == sq) {
      |       ~~~~~~~~~^~~~~
segments.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for (int bl = 0; bl*sq < ol.size(); ++bl) {
      |                     ~~~~~~^~~~~~~~~~~
segments.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for (int i = 0; i < ol.size(); ++i) {
      |                    ~~^~~~~~~~~~~
segments.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for (int bl = 0; bl*sq < ol.size(); ++bl) {
      |                     ~~~~~~^~~~~~~~~~~
segments.cpp: In member function 'int<unnamed struct>::solve(int, int, int)':
segments.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (i = 0; i < u.size(); ++i)
      |               ~~^~~~~~~~~~
segments.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (s = 0; s < ol.size(); s += sq) {
      |               ~~^~~~~~~~~~~
segments.cpp:52:22: warning: unused variable 'S' [-Wunused-variable]
   52 |   int ans = 0, s, f, S, F, i;
      |                      ^
segments.cpp:52:25: warning: unused variable 'F' [-Wunused-variable]
   52 |   int ans = 0, s, f, S, F, i;
      |                         ^
segments.cpp: At global scope:
segments.cpp:86:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main () {
      |       ^

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