Submission #440405

#	Time	Username	Problem	Language	Result	Execution time	Memory
440405		8e7	Segments (IZhO18_segments)	C++14	100 / 100	4849 ms	26652 KiB

segments

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <utility>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int bs = 1500;
const int maxb = maxn / bs + 5;
template<class T> using Tree = tree<T, null_type,less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
Tree<int> lef[maxb], rig[maxb];
pii seg[maxn];
vector<pii> ind[maxb]; // 
pii arr[maxb]; //current block array
int ma[maxb]; // maxsize for each block
int pos[maxn]; // index for segment with id=i
int main() {
	io
	int n, onl;
	cin >> n >> onl;
	int lastans = 0, bind = 1, bcnt = 1, siz = 0, cur = 1;
	while (n--) {
		int type;
		cin >> type;
		if (type == 1) {
			siz++;
			int l, r;
			cin >> l >> r;
			l ^= onl ? lastans : 0, r ^= onl ? lastans : 0;
			if (l > r) swap(l, r);
			int id = cur;
			cur++;
			seg[id] = {l, r};
			int len = r - l + 1;
			for (int i = 0;i < bcnt;i++) {
				if (arr[i].ff <= len || (i == 0 && len > ma[i]) || (i == bcnt - 1)) {
					if (arr[i].ss == 0) arr[i].ss = bind++;
					vector<pii> * tmp = &ind[arr[i].ss];
					tmp->insert(lower_bound(tmp->begin(), tmp->end(), make_pair(len, id), [&](pii x, pii y){return x > y;}), make_pair(len, id)); 
					pos[id] = arr[i].ss;
					lef[arr[i].ss].insert(l);
					rig[arr[i].ss].insert(r);
					arr[i].ff = tmp->back().ff;
					ma[i] = (tmp->begin())->ff;
					if (tmp->size() >= (5 * bs / 2)) { // split a block into two
						for (int j = bcnt;j > i + 1;j--) arr[j] = arr[j - 1], ma[j] = ma[j - 1]; 
						bcnt++;	
						arr[i + 1].ss = bind;
						while (tmp->size() > bs) {
							pii p = tmp->back();
							pos[p.ss] = bind;
							int prv = arr[i].ss;
							lef[prv].erase(lef[prv].upper_bound(seg[p.ss].ff));
							rig[prv].erase(rig[prv].upper_bound(seg[p.ss].ss));
							ind[bind].push_back(p);	
							lef[bind].insert(seg[p.ss].ff);
							rig[bind].insert(seg[p.ss].ss);
							tmp->pop_back();
						}
						reverse(ind[bind].begin(), ind[bind].end());
						arr[i + 1].ff = ind[bind].back().ff;
						ma[i + 1] = ind[bind][0].ff;
						arr[i].ff = ind[arr[i].ss].back().ff;
						bind++;
					}
					break;
				}
			}	
		} else if (type == 2) {
			siz--;
			int id;
			cin >> id;
			int p = pos[id];
			lef[p].erase(lef[p].upper_bound(seg[id].ff));	
			rig[p].erase(rig[p].upper_bound(seg[id].ss));
			for (int i = 0;i < ind[p].size();i++) {
				if (ind[p][i].ss == id) {
					ind[p].erase(ind[p].begin() + i);
					break;
				}
			}
			for (int i = 0;i < bcnt;i++) {
				if (ind[arr[i].ss].size() == 0) {
					for (int j = i + 1;j < bcnt;j++) {
						arr[j - 1] = arr[j];
						ma[j - 1] = ma[j];
					}
					bcnt = max(bcnt - 1, 1);
					break;
				}
			}
			for (int i = 0;i < bcnt;i++) {
				if (arr[i].ss)arr[i].ff = ind[arr[i].ss].back().ff, ma[i] = ind[arr[i].ss][0].ff;
			}
		} else {
			int l, r, k;
			cin >> l >> r >> k;
			l ^= onl ? lastans : 0, r ^= onl ? lastans :0;
			if (l > r) swap(l, r);
			if (r - l + 1 < k) {
				cout << 0 << "\n";
				lastans = 0;
				continue;
			}
			l += k - 1, r -= k - 1; // <l, >r
			int ans = 0;
			for (int i = 0;i < bcnt;i++) {
				if (arr[i].ff < k) {
					for (auto j:ind[arr[i].ss]) {
						if (j.ff < k) continue;
						if (seg[j.ss].ss >= l && seg[j.ss].ff <= r) ans++;
					}	
					break;
				} else {
					ans += ind[arr[i].ss].size();
					ans -= lef[arr[i].ss].size() - lef[arr[i].ss].order_of_key(r + 1);
					ans -= rig[arr[i].ss].order_of_key(l);
				}
			}
			cout << ans << "\n";
			lastans = ans;
		}
		/*
		for (int i = 0;i < bcnt;i++) {
			debug(ma[i]);
			for (auto j:ind[arr[i].ss]) debug(seg[j.ss].ff, seg[j.ss].ss);
			pary(lef[arr[i].ss].begin(), lef[arr[i].ss].end());
			pary(rig[arr[i].ss].begin(), rig[arr[i].ss].end());
		}
		*/
	}
}
/*
6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2

6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1
   */

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for (int i = 0;i < ind[p].size();i++) {
      |                   ~~^~~~~~~~~~~~~~~

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