Submission #339722

#	Time	Username	Problem	Language	Result	Execution time	Memory
339722		GioChkhaidze	Segments (IZhO18_segments)	C++14	0 / 100	5093 ms	31000 KiB

segments

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int inf = 2e9 + 1;
const int N = 2e5 + 5;
const int Sq = 450;

unordered_map < int , int > G;
vector < int > v[Sq][3];
int a[N][3], c[N], A[N], L[Sq][3], R[Sq][3];
int n, t, tot, del, mid, res, ret, lo, hi, sq, ms, as, tp, id, y, bl, j, k, x;

bool cmp1(int x, int y) {
	return a[x][tp] < a[y][tp];
}

bool cmp2(int x, int y) {
	return a[x][1] - a[x][0] < a[y][1] - a[y][0];
}

inline void Restart() {
	for (tp = 0; tp < 2; ++tp) {
		as = 0;
		for (bl = 0; bl < ms; ++bl) {
			for (j = 0; j < v[bl][tp].size(); ++j) 
				A[as++] = v[bl][tp][j];
			v[bl][tp].clear();			
		}
		
		if (as) sort(A , A + as, cmp1);	
		for (j = 0; j < as; ++j) 
			v[(j / sq)][tp].push_back(A[j]);
		
		for (bl = 0; bl < ms; ++bl) {
			if (!v[bl][tp].size()) 
				R[bl][tp] = inf, L[bl][tp] = -inf;
					else
				R[bl][tp] = -inf, L[bl][tp] = inf;
				
			if (!v[bl][tp].size()) continue;	
			sort(v[bl][tp].begin(), v[bl][tp].end(), cmp2);
			for (j = 0; j < v[bl][tp].size(); ++j) {
				y = a[v[bl][tp][j]][tp];		
				if (R[bl][tp] < y) R[bl][tp] = y;
				if (L[bl][tp] > y) L[bl][tp] = y;
			}
		}
	}
}

inline void p() { 
	k = c[id], x = a[id][tp];
	for (bl = 0; bl < ms; ++bl) 
		if (x <= R[bl][tp]) {
			if (!v[bl][tp].size()) R[bl][tp] = L[bl][tp] = x;
					else
			if (x < L[bl][tp]) L[bl][tp] = x;
			
			v[bl][tp].push_back(id);
			j = v[bl][tp].size()-1;
			while (0 < j && c[v[bl][tp][j-1]] > k) 
				swap(v[bl][tp][j-1], v[bl][tp][j]), --j;
			return ;
		}
}

inline void d() { 
	k = c[id], x = a[id][tp];
	for (int bl = 0; bl < ms; ++bl) 
		if (x <= R[bl][tp]) {
			for (int j = 0; j + 1 < v[bl][tp].size(); ++j) 
				if (v[bl][tp][j] == id) swap(v[bl][tp][j], v[bl][tp][j+1]);
			
			v[bl][tp].pop_back();
			if (!v[bl][tp].size()) 
				R[bl][tp] = inf, L[bl][tp] = -inf;
					else
				R[bl][tp] = -inf, L[bl][tp] = inf;
			
			for (int j = 0; j < v[bl][tp].size(); ++j) {
				y = a[v[bl][tp][j]][tp];		
				if (R[bl][tp] < y) R[bl][tp] = y;
				if (L[bl][tp] > y) L[bl][tp] = y;
			}
			return ;
		}
}

int g(int l, int r, int k, bool tp) {
	ret = 0;
	for (bl = 0; bl < ms; ++bl) {
		if (R[bl][tp] < l  || r < L[bl][tp] || !v[bl][tp].size()) continue;
		if (l <= L[bl][tp] && R[bl][tp] <= r) { 
			lo = 0, hi = v[bl][tp].size() - 1, res = 0;
			while (lo <= hi) {
				mid = ((lo + hi) >> 1);
				if (c[v[bl][tp][mid]] < k)
					res = mid + 1, lo = mid + 1;
						else
					hi = mid - 1;
			}
			ret += v[bl][tp].size() - res;
		}
			else {
			for (j = 0; j < v[bl][tp].size(); ++j) { 
				id = v[bl][tp][j];
				if (c[id] < k) continue;
				if (tp && a[id][1] <= r) ++ret;
				if (!tp && l <= a[id][0]) ++ret;
			}		
		}
	}
	return ret;
}

void up(ll x) {
	while (x <= 2e9) {
		G[x] += del;
		x += (x & -x);
	}
} 

int gt(ll x) {
	res = 0;
	while (x > 0) {
		res += G[x];
		x -= (x & -x);
	}
	return res;
}

main () {
	scanf("%d %d",&n, &t);
	sq = sqrt(n);
	ms = (n - 1 + sq - 1) / sq; 
	int lastans = 0, cnt = 0, ans = 0, idx, ty, A, B, C, X, Y, Z;
	for (int i = 0; i < n; ++i) {
		if (!(i % sq)) Restart();
		scanf("%d",&ty);
		if (ty == 1) {
			scanf("%d %d",&a[i][0], &a[i][1]); ++cnt, id = i;
			a[i][0] = (a[i][0] ^ (t * lastans));
			a[i][1] = (a[i][1] ^ (t * lastans));
			if (a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
			c[i] = (a[i][1] - a[i][0] + 1);	
			tp = 0, p();
			tp = 1, p();
			del = 1, up(c[i]);
		}
			else
		if (ty == 2) {
			scanf("%d",&idx); --idx, --cnt, id = idx;
			tp = 0, d();
			tp = 1, d(); 
			del = -1, up(c[idx]);
		}
			else
		if (ty == 3) {
			scanf("%d %d %d",&A, &B, &C);
			A = (A ^ (t * lastans));
			B = (B ^ (t * lastans));
			if (A > B) swap(A, B);
			if (B - A + 1 < C) lastans = ans = 0;
				else {
				X = g(B - C + 2, 2e9, C, 0);    
				Y = g(0, A + C - 2, C, 1); 
				Z = gt(C - 1); 
				lastans = ans = cnt - (X + Y + Z);
			}			
			printf("%d\n",ans);
		}
	}
}

Compilation message (stderr)

segments.cpp: In function 'void Restart()':
segments.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (j = 0; j < v[bl][tp].size(); ++j)
      |                ~~^~~~~~~~~~~~~~~~~~
segments.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (j = 0; j < v[bl][tp].size(); ++j) {
      |                ~~^~~~~~~~~~~~~~~~~~
segments.cpp: In function 'void d()':
segments.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for (int j = 0; j + 1 < v[bl][tp].size(); ++j)
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~
segments.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for (int j = 0; j < v[bl][tp].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int g(int, int, int, bool)':
segments.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for (j = 0; j < v[bl][tp].size(); ++j) {
      |                ~~^~~~~~~~~~~~~~~~~~
segments.cpp: At global scope:
segments.cpp:135:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  135 | main () {
      |       ^
segments.cpp: In function 'int main()':
segments.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |  scanf("%d %d",&n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |   scanf("%d",&ty);
      |   ~~~~~^~~~~~~~~~
segments.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  144 |    scanf("%d %d",&a[i][0], &a[i][1]); ++cnt, id = i;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:155:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |    scanf("%d",&idx); --idx, --cnt, id = idx;
      |    ~~~~~^~~~~~~~~~~
segments.cpp:162:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |    scanf("%d %d %d",&A, &B, &C);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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