Submission #385581

#	Time	Username	Problem	Language	Result	Execution time	Memory
385581		patrikpavic2	Segments (IZhO18_segments)	C++17	75 / 100	5062 ms	15684 KiB

segments

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

#define PB push_back

using namespace std;

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

int un[N], n, vel, L[N], R[N], lg2[N];
int br_buk = 0, mi[N], mx[N], q;
vector < int > po_L[N], po_R[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(vector < int > &v, int x){
	int ret = -1;
	for(int i = lg2[(int)v.size()];i >= 0;i--){
		if(ret + (1 << i) < (int)v.size() && L[v[ret + (1 << i)]] > x)
			ret += (1 << i);
	}
	return ret + 1;
}

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



void rebuild(){
	vector < int > svi;
	for(int i = 0;i < vel;i++){
		if(un[i]) svi.PB(i);
		mi[i] = INF, mx[i] = -INF;
		po_L[i].clear(); po_R[i].clear();
	}
	sort(svi.begin(), svi.end(), cmp_len);
	int cur = 0; br_buk = 0;
	for(int x : svi){
		po_L[cur / BUK].PB(x);
		po_R[cur / BUK].PB(x);
		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].begin(), po_L[i].end(), cmpL);
		sort(po_R[i].begin(), po_R[i].end(), cmpR);
	}
}

vector < int > pos_ubac, pos_izbac;
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){
			pos_ubac.clear();
			pos_izbac.clear();
			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);
				}
				else{
					for(int x : po_L[i]) sol += dobar(x);
				}
			}
			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:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  int T; scanf("%d%d", &q, &T);
      |         ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:92:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
segments.cpp:94:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |    int l, r; scanf("%d%d", &l, &r);
      |              ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:101:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
segments.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |    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: 0 / 25