Submission #340145

#	Time	Username	Problem	Language	Result	Execution time	Memory
340145		GioChkhaidze	Segments (IZhO18_segments)	C++14	0 / 100	348 ms	4840 KiB

segments

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

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

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

bool cmp(int x, int y) {
	return C[x] < C[y];
}

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

	void insert(int id) {
		u.pb(id);
		if (u.size() == sq) {
			c.reserve(u.size() + ol.size());
			sort(u.begin(), u.end(), cmp);
			merge(u.begin(), u.end(), ol.begin(), ol.end(), back_inserter(c));
			ol.swap(c), c.clear(), 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 = ol[i] / sq;
				L[bl].pb(A[ol[i]]);
				R[bl].pb(B[ol[i]]);
			}
			
			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]]) - max(l, A[u[i]]) + 1 >= k) 
				++ans;
		
		for (s = 0; s < ol.size(); s += sq) {
			f = min(s + bl - 1, (int)ol.size() - 1);
			S = ol[s], F = ol[f];
		
			if (B[F] - A[F] + 1 >= 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 (B[S] - A[S] + 1 >= k) {
				for (i = s; i <= f; ++i) 
					if (min(r, B[u[i]]) - max(l, A[u[i]]) + 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;
	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]);
			cur.insert(u), ++u;
		}
			else
		if (ty == 2) { 
			cin >> id; --id;
			rcur.insert(id);
		}
			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:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
segments.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("Ofast")
      | 
segments.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
segments.cpp: In member function 'void<unnamed struct>::insert(int)':
segments.cpp:29:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   if (u.size() == sq) {
      |       ~~~~~~~~~^~~~~
segments.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for (int bl = 0; bl*sq < ol.size(); ++bl) {
      |                     ~~~~~~^~~~~~~~~~~
segments.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int i = 0; i < ol.size(); ++i) {
      |                    ~~^~~~~~~~~~~
segments.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (int bl = 0; bl*sq < ol.size(); ++bl) {
      |                     ~~~~~~^~~~~~~~~~~
segments.cpp: In member function 'int<unnamed struct>::solve(int, int, int)':
segments.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (i = 0; i < u.size(); ++i)
      |               ~~^~~~~~~~~~
segments.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (s = 0; s < ol.size(); s += sq) {
      |               ~~^~~~~~~~~~~
segments.cpp: At global scope:
segments.cpp:89:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main () {
      |       ^

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