Submission #339920

#	Time	Username	Problem	Language	Result	Execution time	Memory
339920		GioChkhaidze	Segments (IZhO18_segments)	C++14	75 / 100	5075 ms	21868 KiB

segments

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define ll long long
#define ordered_set tree < pair < int , int > , null_type,less < pair<int, int> > , rb_tree_tag,tree_order_statistics_node_update> 
  
using namespace std;
using namespace __gnu_pbds;

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

int v[Sq][2][3033], vs[Sq][2], a[N][2], pr[N][2], c[N], A[N], L[Sq][2], R[Sq][2], Rm[Sq][2], B[3033];
int n, t, tot, del, mid, res, ret, lo, hi, sq, Lq, Rq, Kq, ms, as, tp, id, x, y, bl, j, k;

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

bool cmp2(int x, int y) {
	return c[x] < c[y];
}

inline void Restart() {
	for (tp = 0; tp < 2; ++tp) {
		as = 0;
		for (bl = 0; bl < ms; ++bl) {
			if (!vs[bl][tp]) continue;
			for (j = 0; j < vs[bl][tp]; ++j) 
				B[j] = v[bl][tp][j];
				
			sort(B, B + vs[bl][tp], cmp1);
			for (j = 0; j < vs[bl][tp]; ++j) 
				A[as++] = B[j];
				
			vs[bl][tp] = 0;		
		}
		
		for (j = 0; j < as; ++j) {
			bl = j / sq;
			v[bl][tp][vs[bl][tp]++] = A[j];
			pr[A[j]][tp] = bl;
		}
		
		for (bl = 0; bl < ms; ++bl) {
			Rm[bl][tp] = -1, R[bl][tp] = 0, L[bl][tp] = inf;	
			if (!vs[bl][tp]) continue;
			for (j = 0; j < vs[bl][tp]; ++j) {
				y = a[v[bl][tp][j]][tp];	
				A[j] = v[bl][tp][j];	
				if (Rm[bl][tp] < y) R[bl][tp] = Rm[bl][tp] = y;
				if (L[bl][tp] > y) L[bl][tp] = y;
			}
			
			sort(A, A + vs[bl][tp], cmp2);
			for (j = 0; j < vs[bl][tp]; ++j) 
				v[bl][tp][j] = A[j];	
		}
	}
}

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

inline void d() { 
	k = c[id], x = a[id][tp];
	for (bl = 0; bl < ms; ++bl) 
		if (pr[id][tp] == bl) {
			R[bl][tp] = 0, L[bl][tp] = inf;
			for (j = 0; j + 1 < vs[bl][tp]; ++j) {
				if (v[bl][tp][j] == id) swap(v[bl][tp][j], v[bl][tp][j + 1]);
				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;
			}
			--vs[bl][tp];
			return ;
		}
}

int g() {
	ret = 0;
	if (Lq > Rq) return 0;
	for (bl = 0; bl < ms; ++bl) {
		if (!vs[bl][tp]) continue;
		if (Rm[bl][tp] == -1) break;
		if (tp && Rq < L[bl][tp]) break;
		if (R[bl][tp] < Lq  || Rq < L[bl][tp]) continue;
		if (Lq <= L[bl][tp] && R[bl][tp] <= Rq) { 
			lo = 0, hi = vs[bl][tp] - 1, res = 0;
			while (lo <= hi) {
				mid = ((lo + hi) >> 1);
				if (c[v[bl][tp][mid]] < Kq)
					res = lo = mid + 1;
						else
					hi = mid - 1;
			}
			ret += vs[bl][tp] - res;
		}
			else {
			for (j = vs[bl][tp] - 1; j >= 0; --j) { 
				id = v[bl][tp][j];
				if (c[id] < Kq) break;
				if (tp && a[id][1] <= Rq) ++ret;
				if (!tp && Lq <= a[id][0]) ++ret;
			}	
		}
	}
	return ret;
}

main () {
	ordered_set o;
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> t;
	sq = 1500, ms = 140; 
	int lastans = 0, ans = 0, cnt = 0, u = 0, idx, ty, X, Y, Z, A, B, C;
	for (int i = 0; i < n; ++i) {
		cin >> ty;
		if (ty == 1) {
			if (!(u % sq)) Restart();
			id = ++u, ++cnt;
			cin >> a[u][0] >> a[u][1];
			a[u][0] = (a[u][0] ^ (t * lastans));
			a[u][1] = (a[u][1] ^ (t * lastans));
			if (a[u][0] > a[u][1]) swap(a[u][0], a[u][1]);
			c[u] = (a[u][1] - a[u][0] + 1);	
			tp = 0, p(), tp = 1, p();
			o.insert({c[u],u});
		}
			else
		if (ty == 2) {
			cin >> idx; --cnt, id = idx;
			tp = 0, d(), tp = 1, d(); 
			o.erase({c[id],id});
		}
			else
		if (ty == 3) {
			cin >> 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 {
				tp = 0, Lq = B - C + 2, Rq = inf, Kq = C, X = g();   
				tp = 1, Lq = 0, Rq = A + C - 2, Kq = C, Y = g(); 
				Z = o.order_of_key({C,-1}); 
				lastans = ans = cnt - (X + Y + Z);
			}			
			cout << ans << "\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:133:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main () {
      |       ^

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