Submission #797453

#	Time	Username	Problem	Language	Result	Execution time	Memory
797453		kingfran1907	Segments (IZhO18_segments)	C++14	0 / 100	178 ms	53680 KiB

segments

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;
const llint off = 1LL << 32;
const int maxn = 2e5+10;

struct node {
	int val;
	node *l, *r;
	
	node() {
		val = 0;
		l = r = nullptr;
	}
};
typedef node* pnode;

int value(pnode tren) {
	if (tren == nullptr) return 0;
	return tren->val;
}

pnode L(pnode tren) {
	if (tren == nullptr) return nullptr;
	return tren->l;
}

pnode R(pnode tren) {
	if (tren == nullptr) return nullptr;
	return tren->r;
}

int n, t;
set< int > s;
pnode lef, rig;
pair<llint, llint> niz[maxn];

void update(llint x, llint l, llint r, pnode tren, int val) {
	//printf("update: %lld %lld %lld %d %d\n", x, l, r, tren, val);
	if (x < l || x > r) return;
	if (l == r) {
		tren->val += val;
		return;
	}
	
	int mid = (l + r) / 2;
	if (x <= mid) {
		if (tren->l == nullptr) tren->l = new node();
		update(x, l, mid, tren->l, val);
	} else {
		if (tren->r == nullptr) tren->r = new node();
		update(x, mid + 1, r, tren->r, val);
	}
	tren->val = value(tren->l) + value(tren->r);
}

int query(llint a, llint b, llint l, llint r, pnode node) {
	if (l > b || r < a) return 0;
	if (node == nullptr) return 0;
	if (l >= a && r <= b) return value(node);
	
	int mid = (l + r) / 2;
	return query(a, b, l, mid, node->l) + query(a, b, mid + 1, r, node->r);
}

int main() {
	scanf("%d%d", &n, &t);
	for (int i = 1; i <= n + 2; i++)
		s.insert(i);
	//printf("off: %lld\n", off);
	
	int lastans = 0;
	lef = new node();
	rig = new node();
	int cnt = 0;
	while (n--) {
		int type;
		scanf("%d", &type);
		if (type == 1) {
			llint l, r;
			scanf("%lld%lld", &l, &r);
			l = l ^ (t * lastans);
			r = r ^ (t * lastans);
			if (l > r) swap(l, r); 
			
			int ind = *s.begin();
			s.erase(s.begin()); cnt++;
			
			update(r, 0, off - 1, lef, 1);
			update(l, 0, off - 1, rig, 1);
			niz[ind] = {l, r};
		} else if (type == 2) {
			int id;
			scanf("%d", &id);
			llint l = niz[id].X, r = niz[id].Y;
			
			update(r, 0, off - 1, lef, -1);
			update(l, 0, off - 1, rig, -1);
			s.insert(id); cnt--;
		} else {
			llint l, r, k;
			scanf("%lld%lld%lld", &l, &r, &k);
			l = l ^ (t * lastans); l--;
			r = r ^ (t * lastans); r++;
			if (l > r) swap(l, r);
			
			lastans = cnt;
			lastans -= query(0, l, 0, off - 1, lef);
			lastans -= query(r, off - 1, 0, off - 1, rig);
			printf("%d\n", lastans);
		}
	}
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d", &type);
      |   ~~~~~^~~~~~~~~~~~~
segments.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    scanf("%lld%lld", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |    scanf("%d", &id);
      |    ~~~~~^~~~~~~~~~~
segments.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%lld%lld%lld", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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