Submission #379665

#	Time	Username	Problem	Language	Result	Execution time	Memory
379665		cheissmart	Segments (IZhO18_segments)	C++14	Compilation error	0 ms	0 KiB

segments

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7, K = 2000;

pi seg[N];
V<array<int, 3>> buf;
int alive[N], new_id = 1;
int tot = 0;
vi r_bucket[N / K + 1], l_bucket[N / K + 1];
V<array<int, 3>> all;

void rebuild() {
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++)
		l_bucket[i].clear(), r_bucket[i].clear();
	tot = 0;
	all.clear();
	for(int i = 1; i < new_id; i++) if(alive[i]) {
		tot++;
		int l = seg[i].F, r = seg[i].S;
		all.PB({r - l, l, r});
	}
	sort(ALL(all));
	for(int i = 0; i < tot; i++) {
		l_bucket[i / K].PB(all[i][1]);
		r_bucket[i / K].PB(all[i][2]);
	}
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
		sort(ALL(l_bucket[i]));
		sort(ALL(r_bucket[i]));
	}
	buf.clear();
}

void add(int l, int r) {
	alive[new_id] = 1;
	seg[new_id] = {l, r};
	buf.PB({seg[new_id].F, seg[new_id].S, 1});
	new_id++;
	if(buf.size() > K) rebuild();
}

void del(int id) {
	alive[id] = 0;
	buf.PB({seg[id].F, seg[id].S, -1});
	if(buf.size() > K) rebuild();
}

int qry(int l, int r, int k) { // k is length
	if(r - l < k) return 0;
	int ans = tot;
	if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
		int lb = i * K, rb = min((i + 1) * K, tot);
		// if(all[rb - 1][0] < k) {
		// 	ans -= int(l_bucket[i].size());
		// 	continue;
		}
		if(all[lb][0] >= k && false) {
			ans -= lower_bound(ALL(r_bucket[i]), l + k) - r_bucket[i].begin();
			ans -= int(l_bucket[i].size()) - (upper_bound(ALL(l_bucket[i]), r - k) - l_bucket[i].begin());
		} else {
			for(int j = lb; j < rb; j++) if(all[j][0] >= k) {
				if(all[j][2] < l + k) ans--;
				if(all[j][1] > r - k) ans--;
			}
		}
	}
	for(auto p:buf) {
		int L = max(l, p[0]), R = min(r, p[1]);
		if(R - L >= k)
			ans += p[2];
	}
	return ans;
}

signed main()
{
	IO_OP;

	int n, t;
	cin >> n >> t;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int op;
		cin >> op;
		auto decode = [&] (int& a, int& b) {
			a ^= t * ans, b ^= t * ans;
			if(a > b) swap(a, b);
		};
		if(op == 1) {
			int a, b;
			cin >> a >> b;
			decode(a, b);
			add(a, b);
		} else if(op == 2) {
			int id;	
			cin >> id;
			del(id);
		} else {
			int a, b, k;
			cin >> a >> b >> k;
			decode(a, b);
			ans = qry(a, b, k - 1);
			cout << ans << '\n';
		}
	}
	
}

Compilation message (stderr)

segments.cpp: In function 'int qry(int, int, int)':
segments.cpp:67:7: warning: unused variable 'lb' [-Wunused-variable]
   67 |   int lb = i * K, rb = min((i + 1) * K, tot);
      |       ^~
segments.cpp:67:19: warning: unused variable 'rb' [-Wunused-variable]
   67 |   int lb = i * K, rb = min((i + 1) * K, tot);
      |                   ^~
segments.cpp:66:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   66 |  if(tot) for(int i = 0; i <= (tot - 1) / K; i++) {
      |  ^~
segments.cpp:72:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   72 |   if(all[lb][0] >= k && false) {
      |   ^~
segments.cpp:72:10: error: 'lb' was not declared in this scope; did you mean 'l'?
   72 |   if(all[lb][0] >= k && false) {
      |          ^~
      |          l
segments.cpp:73:36: error: 'i' was not declared in this scope
   73 |    ans -= lower_bound(ALL(r_bucket[i]), l + k) - r_bucket[i].begin();
      |                                    ^
segments.cpp:9:17: note: in definition of macro 'ALL'
    9 | #define ALL(v) (v).begin(), (v).end()
      |                 ^
segments.cpp:76:24: error: 'rb' was not declared in this scope; did you mean 'r'?
   76 |    for(int j = lb; j < rb; j++) if(all[j][0] >= k) {
      |                        ^~
      |                        r
segments.cpp: At global scope:
segments.cpp:82:2: error: expected unqualified-id before 'for'
   82 |  for(auto p:buf) {
      |  ^~~
segments.cpp:87:2: error: expected unqualified-id before 'return'
   87 |  return ans;
      |  ^~~~~~
segments.cpp:88:1: error: expected declaration before '}' token
   88 | }
      | ^
segments.cpp: In function 'int qry(int, int, int)':
segments.cpp:81:2: warning: control reaches end of non-void function [-Wreturn-type]
   81 |  }
      |  ^