Submission #1087733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087733		xnqs	Segments (IZhO18_segments)	C++17	0 / 100	28 ms	2908 KiB

segments

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>

template<typename Type>
class FenwickTree {
private:
	std::vector<Type> bit;
public:
	FenwickTree(int size = 0, Type val = 0) {
		assign(size,val);
	}
	void assign(int size = 0, Type val = 0) {
		bit.assign(size,0);
		if (size&&val) {
			for (int i = 1; i < size; i++) {
				bit[i] += val;
				if (i+(i&-i)<bit.size()) {
					bit[i+(i&-i)] += bit[i];
				}
			}
		}
	}

	void add(int poz, Type val) {
		while (poz<bit.size()) {
			bit[poz] += val;
			poz += poz&-poz;
		}
	}

	Type query(int poz) {
		Type ret = 0;
		while (poz>0) {
			ret += bit[poz];
			poz ^= poz&-poz;
		}
		return ret;
	}

	Type query(int l, int r) {
		return query(r) - query(l-1);
	}

	int binary_lifting(Type val) {
		int ret = 0;
		for (int step = 1<<18; step; step >>= 1) {
			if (ret+step<bit.size()&&val-bit[ret+step]>0) {
				val -= bit[ret+step];
				ret += step;
			}
		}
		return ++ret;
	}
};

int q, t;
std::pair<int,int> seg[5005];
std::map<std::pair<int,int>,int> map;
FenwickTree<int> fnwk(200005,1);
bool active[5005];

int intersection_size(int l1, int r1, int l2, int r2) {
	return std::min(r1,r2) - std::max(l1,l2) + 1;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> q >> t;
	int last_ans = 0;
	while (q--) {
		int op;
		std::cin >> op;
		if (op==1) {
			int a, b;
			std::cin >> a >> b;

			int l = a^(t*last_ans);
			int r = b^(t*last_ans);
			if (l>r) std::swap(l,r);

			int idx = fnwk.binary_lifting(1);
			fnwk.add(idx,-1);
			seg[idx] = std::pair<int,int>(l,r);
			map[std::pair<int,int>(l,r)] = idx;
			active[idx] = 1;
		}
		else if (op==2) {
			int idx;
			std::cin >> idx;

			fnwk.add(idx,1);
			active[idx] = 0;
		}
		else {
			int a, b, k;
			std::cin >> a >> b >> k;

			int l = a^(t*last_ans);
			int r = b^(t*last_ans);
			if (l>r) std::swap(l,r);

			int ret = 0;
			for (int i = 0; i < 5000; i++) {
				if (active[i]) {
					ret += (intersection_size(l,r,seg[i].first,seg[i].second) >= k);
				}
			}

			last_ans = ret;
			std::cout << ret << "\n";
		}
	}
}

Compilation message (stderr)

segments.cpp: In instantiation of 'int FenwickTree<Type>::binary_lifting(Type) [with Type = int]':
segments.cpp:89:35:   required from here
segments.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if (ret+step<bit.size()&&val-bit[ret+step]>0) {
      |        ~~~~~~~~^~~~~~~~~~~
segments.cpp: In instantiation of 'void FenwickTree<Type>::add(int, Type) [with Type = int]':
segments.cpp:90:19:   required from here
segments.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   while (poz<bit.size()) {
      |          ~~~^~~~~~~~~~~
segments.cpp: In instantiation of 'void FenwickTree<Type>::assign(int, Type) [with Type = int]':
segments.cpp:15:3:   required from 'FenwickTree<Type>::FenwickTree(int, Type) [with Type = int]'
segments.cpp:64:31:   required from here
segments.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if (i+(i&-i)<bit.size()) {
      |         ~~~~~~~~^~~~~~~~~~~

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