oj.uz

Submission #41721

# Submission time Handle Problem Language Result Execution time Memory
41721 2018-02-21T04:14:15 Z aome Segments (IZhO18_segments) C++14
0 / 100
 5000 ms 1316 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const int B = 1000;

int n, t, sz, lastans;
int cnt;
int L[N], R[N];
bool del[N];
vector<int> buf_add;
vector<int> buf_del;
vector<int> block_l[500];
vector<int> block_r[500];
vector< pair<int, int> > go;

void prep() {
	go.clear();
	for (int i = 1; i <= sz; ++i) {
		if (!del[i]) go.push_back(make_pair(R[i] - L[i] + 1, i));
	}
	sort(go.begin(), go.end());
	buf_add.clear(), buf_del.clear();
	int m = go.size();
	for (int i = 0; i <= m / B; ++i) block_l[i].clear(), block_r[i].clear();
	for (int i = 0; i < m; ++i) block_l[i / B].push_back(L[go[i].second]);
	for (int i = 0; i < m; ++i) block_r[i / B].push_back(R[go[i].second]); 
	for (int i = 0; i <= m / B; ++i) {
		sort(block_l[i].begin(), block_l[i].end());
		sort(block_r[i].begin(), block_r[i].end());
	}
}

int calc(int id, int l, int r) {
	// count number of commont points betweeen L[id], R[id] and l, r
	if (L[id] > l) return max(0, min(r, R[id]) - L[id] + 1);
	return max(0, min(R[id], r) - l + 1);
}

int calL(int l, int r, int x) {
	// count number of segments from l -> r which has L > x
	int res = 0;
	int bl = l / B, br = r / B;
	if (bl == br) {
		for (int i = l; i <= r; ++i) res += L[go[i].second] > x;
		return res;
	}
	for (int i = bl + 1; i < br; ++i) {
		int tmp = lower_bound(block_l[i].begin(), block_l[i].end(), x + 1) - block_l[i].begin();
		res += B - tmp + 1;
	}
	for (int i = l; i < (bl + 1) * B; ++i) res += L[go[i].second] > x;
	for (int i = br * B; i <= r; ++i) res += L[go[i].second] > x;
	return res;
}

int calR(int l, int r, int x) {
	// count number of segments from l -> r which has R < x
	int res = 0;
	int bl = l / B, br = r / B;
	if (bl == br) {
		for (int i = l; i <= r; ++i) res += R[go[i].second] < x;
		return res;
	}
	for (int i = bl + 1; i < br; ++i) {
		int tmp = lower_bound(block_r[i].begin(), block_r[i].end(), x) - block_r[i].begin();
		res += tmp;
	}
	for (int i = l; i < (bl + 1) * B; ++i) res += R[go[i].second] < x;
	for (int i = br * B; i <= r; ++i) res += R[go[i].second] < x;
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> t;
	for (int i = 1; i <= n; ++i) {
		if (i % 1 == 0) prep();

		int type; cin >> type;

		if (type == 1) {
			int l, r; cin >> l >> r;
			l = l ^ (1LL * t * lastans);
			r = r ^ (1LL * t * lastans);
			if (l > r) swap(l, r);
			++sz, L[sz] = l, R[sz] = r, buf_add.push_back(sz), cnt++;
		}

		if (type == 2) {
			int x; cin >> x, buf_del.push_back(x), del[x] = 1, cnt--;
		}

		if (type == 3) {
			int l, r, k; 
			cin >> l >> r >> k;
			l = l ^ (1LL * t * lastans);
			r = r ^ (1LL * t * lastans);
			if (l > r) swap(l, r);

			if (r - l + 1 < k) {
				lastans = 0, cout << "0\n"; continue;
			} 

			int res = 0;	

			// cout << "#add\n";
			// for (auto j : buf_add) cout << j << ' '; cout << '\n';
			// cout << "#del\n";
			// for (auto j : buf_del) cout << j << ' '; cout << '\n';

			for (auto j : buf_add) res += calc(j, l, r) < k;
			for (auto j : buf_del) res -= calc(j, l, r) < k;
			int p = lower_bound(go.begin(), go.end(), make_pair(k, 0)) - go.begin();

			// cout << "#go\n";
			// for (auto i : go) cout << i.second << ' '; cout << '\n';
			// cout << "#p " << p << '\n';

			// number of segments r - l + 1 < k
			res += p;

			// query p -> sz (segments with size >= k)

			// count number of segments L > r - k + 1
			res += calL(p, go.size() - 1, r - k + 1);
			// count number of segments R < l + k - 1
			res += calR(p, go.size() - 1, l + k - 1);

			// cout << "#l-r " << l << ' ' << r << '\n';
			// cout << "# " << res << '\n';

			res = cnt - res, lastans = res;
			cout << res << '\n';
		}
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 16 ms 532 KB Output is correct
4 Correct 15 ms 532 KB Output is correct
5 Incorrect 2283 ms 864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 1072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3924 ms 1268 KB Output is correct
2 Correct 2352 ms 1268 KB Output is correct
3 Execution timed out 5040 ms 1296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2346 ms 1312 KB Output is correct
2 Correct 2497 ms 1316 KB Output is correct
3 Correct 2381 ms 1316 KB Output is correct
4 Correct 2989 ms 1316 KB Output is correct
5 Execution timed out 5074 ms 1316 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 16 ms 532 KB Output is correct
4 Correct 15 ms 532 KB Output is correct
5 Incorrect 2283 ms 864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 16 ms 532 KB Output is correct
4 Correct 15 ms 532 KB Output is correct
5 Incorrect 2283 ms 864 KB Output isn't correct
6 Halted 0 ms 0 KB -