Submission #385597

#	Time	Username	Problem	Language	Result	Execution time	Memory
385597		patrikpavic2	Segments (IZhO18_segments)	C++17	100 / 100	3358 ms	13000 KiB

segments

#include <cstdio>
#include <vector>
#include <algorithm>

#define PB push_back

using namespace std;

const int N = 2e5 + 500;
const int INF = 0x3f3f3f3f;
const int BUK = 2000;
const int UPD = 2000;

int un[N], n, vel, L[N], R[N], lg2[N];
int br_buk = 0, mi[N], mx[N], q;
int po_L[N], po_R[N], sz[N];

bool cmp_len(int x, int y){
	return R[x] - L[x] < R[y] - L[y];
}

bool cmpL(int x, int y){
	return L[x] > L[y];
}

bool cmpR(int x, int y){
	return R[x] < R[y];
}

int losihL(int *v, int x, int vel){
	int ret = -1;
	for(int i = lg2[vel];i >= 0;i--){
		if(ret + (1 << i) < vel && L[v[ret + (1 << i)]] > x)
			ret += (1 << i);
	}
	return ret + 1;
}

int losihR(int *v, int x, int vel){
	int ret = -1;
	for(int i = lg2[vel];i >= 0;i--){
		if(ret + (1 << i) < vel && R[v[ret + (1 << i)]] < x)
			ret += (1 << i);
	}
	return ret + 1;
}

vector < int > svi;
vector < int > pos_ubac, pos_izbac;



void rebuild(){
	vector < int > nov;
	sort(pos_ubac.begin(), pos_ubac.end(), cmp_len);
	int i = 0, j = 0;
	for(;i < (int)svi.size() || j < (int)pos_ubac.size();){
		int nxt = 0;
		if(i == (int)svi.size()) nxt = pos_ubac[j++];
		else if(j == (int)pos_ubac.size()) nxt = svi[i++];
		else if(cmp_len(svi[i], pos_ubac[j])) nxt = svi[i++];
		else nxt = pos_ubac[j++];
		if(un[nxt]) nov.PB(nxt);
	}
	pos_ubac.clear(); pos_izbac.clear();
	svi = nov;
	//printf("SVI = %d\n", (int)svi.size());
	for(int i = 0;i < br_buk;i++){
		mi[i] = INF, mx[i] = -INF; sz[i] = 0;
	}
	int cur = 0; br_buk = 0;
	for(int x : svi){
		//printf("%d %d\n", L[x], R[x]);
		po_L[cur] = x;
		po_R[cur] = x;
		sz[cur / BUK]++;
		mi[cur / BUK] = min(mi[cur / BUK], R[x] - L[x]);
		mx[cur / BUK] = max(mx[cur / BUK], R[x] - L[x]);
		br_buk = (cur++) / BUK + 1;
	}
	for(int i = 0;i < br_buk;i++){
		sort(po_L + i * BUK, po_L + i * BUK + sz[i], cmpL);
		sort(po_R + i * BUK, po_R + i * BUK + sz[i], cmpR);
	}
}

int l, r, k;

bool dobar(int x){
	return L[x] <= r - k && R[x] >= l + k && R[x] - L[x] >= k;
}

int main(){
	for(int i = 0;i < N;i++){
		while((1 << lg2[i]) <= i) lg2[i]++;
		lg2[i]--;
	}
	int T; scanf("%d%d", &q, &T);
	int sol = 0;
	for(;q--;){
		if(q % UPD == 0){
			rebuild();
		}
		int ty; scanf("%d", &ty);
		if(ty == 1){
			int l, r; scanf("%d%d", &l, &r);
			l = (l ^ (T * sol)), r = (r ^ (T * sol));
			if(l > r) swap(l, r);
			L[vel] = l, R[vel] = r; un[vel] = 1;
			pos_ubac.PB(vel); vel++;
		}
		if(ty == 2){
			int x; scanf("%d", &x);
			pos_izbac.PB(x - 1); un[x - 1] = 0;
		}
		if(ty == 3){
			scanf("%d%d%d", &l, &r, &k); k--;
			l = (l ^ (T * sol)), r = (r ^ (T * sol)); sol = 0;
			if(l > r) swap(l, r);
			if(r - l < k){
				printf("%d\n", sol);
				continue;
			}
			for(int i = 0;i < br_buk;i++){
				if(mx[i] < k) continue;
				if(mi[i] >= k){
					//printf("sol += %d - %d - %d\n", (int)po_L[i].size(), losihL(po_L[i], r - k), losihR(po_R[i], l + k));
					//sol += (int)po_L[i].size() - losihL(po_L[i], r - k) - losihR(po_R[i], l + k);
					sol += sz[i];
					sol -= losihL(po_L + i * BUK, r - k, sz[i]);
					sol -= losihR(po_R + i * BUK, l + k, sz[i]);
				}
				else{
					for(int j = 0;j < sz[i];j++) sol += dobar(po_L[i * BUK + j]);
				}
			}
			for(int x : pos_ubac) sol += dobar(x);
			for(int x : pos_izbac) sol -= dobar(x);
			printf("%d\n", sol);
		}

	}
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  int T; scanf("%d%d", &q, &T);
      |         ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:104:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
segments.cpp:106:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |    int l, r; scanf("%d%d", &l, &r);
      |              ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:113:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
segments.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |    scanf("%d%d%d", &l, &r, &k); k--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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