Submission #340149

#	Time	Username	Problem	Language	Result	Execution time	Memory
340149		GioChkhaidze	Segments (IZhO18_segments)	C++14	23 / 100	5034 ms	5508 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 = 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 + sq - 1, (int)ol.size() - 1);
			S = ol[s], F = ol[f];

			if (C[S] >= 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[F] >= k) {
				for (i = s; i <= f; ++i) 
					if (min(r, B[ol[i]]) - max(l, A[ol[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 () {
	scanf("%d %d",&n, &t);
	int ty, id, l, r, k;
	for (int i = 0; i < n; ++i) {
		scanf("%d",&ty);
		if (ty == 1) { 
			scanf("%d %d",&A[u],&B[u]);
			C[u] = G(A[u], B[u]);
			cur.insert(u), ++u;
		}
			else
		if (ty == 2) { 
			scanf("%d",&id); --id;
			rcur.insert(id);
		}
			else
		if (ty == 3) { 
			scanf("%d %d %d",&l, &r, &k); G(l, r);
			lastans = cur.solve(l, r, k) - rcur.solve(l, r, k);
			printf("%d\n", lastans);
		}
	}
}

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 () {
      |       ^
segments.cpp: In function 'int main()':
segments.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d %d",&n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%d",&ty);
      |   ~~~~~^~~~~~~~~~
segments.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |    scanf("%d %d",&A[u],&B[u]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~
segments.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |    scanf("%d",&id); --id;
      |    ~~~~~^~~~~~~~~~
segments.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |    scanf("%d %d %d",&l, &r, &k); G(l, r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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