oj.uz

Submission #908499

# Submission time Handle Problem Language Result Execution time Memory
908499 2024-01-16T13:04:02 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 58524 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define isz(a) (int)(a).size()

const int NM = 2e5, BL = 2000;

int n, t, type[NM+5], a[NM+5], b[NM+5], id[NM+5], k[NM+5], lastans = 0;
int num = 0, l[NM+5], r[NM+5];
bool del[NM+5];
int sz;
vector <int> arr;
vector <int> node1[NM+5], node2[NM+5], bit1[NM+5], bit2[NM+5];
int cnt[NM+5];

void fake_update(vector <int> node[NM+5], int x, int y){
	while (x <= sz){
		node[x].push_back(y);
		x += x & (-x);
	}
}

void update(vector <int> node[NM+5], vector <int> bit[NM+5], int x, int yy){
	while (x <= sz){
		int y = lower_bound(node[x].begin(), node[x].end(), yy)-node[x].begin()+1;
		while (y <= isz(node[x])){
			bit[x][y]++;
			y += y & (-y);
		}
		x += x & (-x);
	}
}

void update_cnt(int x){
	while (x <= sz){
		cnt[x]++;
		x += x & (-x);
	}
}

int find_pos(vector <int> &v, int x){
	if (v.empty()) return 0;
	if (x < v[0]) return 0;
	if (x >= v.back()) return isz(v);
	return upper_bound(v.begin(), v.end(), x)-v.begin();
}

int get(vector <int> node[NM+5], vector <int> bit[NM+5], int x, int yy){
	int res = 0;
	while (x > 0){
		int y = find_pos(node[x], yy);
		while (y > 0){
			res += bit[x][y];
			y -= y & (-y);
		}
		x -= x & (-x);
	}
	return res;
}

int get_cnt(int x){
	int res = 0;
	while (x > 0){
		res += cnt[x];
		x -= x & (-x);
	}
	return res;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> t;
	for (int i = 0; i < n; i++){
		cin >> type[i];
		if (type[i] == 1){
			cin >> a[i] >> b[i];
			a[i] ^= (t*lastans), b[i] ^= (t*lastans);
			if (a[i] > b[i]) swap(a[i], b[i]);
			l[++num] = a[i], r[num] = b[i];
		}
		else if (type[i] == 2){
			cin >> id[i];
			del[id[i]] = 1;
		}
		else{
			cin >> a[i] >> b[i] >> k[i];
			a[i] ^= (t*lastans), b[i] ^= (t*lastans);
			if (a[i] > b[i]) swap(a[i], b[i]);
			lastans = get_cnt(find_pos(arr, -k[i]))-get(node1, bit1, find_pos(arr, -k[i]), -b[i]+k[i]-2)-get(node2, bit2, find_pos(arr, -k[i]), a[i]+k[i]-2);
			for (int j = i-i%BL; j < i; j++){
				if (type[j] == 1){
					int lo = max(a[j], a[i]), hi = min(b[j], b[i]);
					if (hi-lo+1 >= k[i]) lastans++;
				}
				else if (type[j] == 2){
					int lo = max(l[id[j]], a[i]), hi = min(r[id[j]], b[i]);
					if (hi-lo+1 >= k[i]) lastans--;
				}
			}
			cout << lastans << '\n';
		}
		if (i%BL == BL-1 && i < n-1){
			arr.clear();
			for (int j = 1; j <= num; j++)
				if (!del[j]){
					arr.push_back(-(r[j]-l[j]+1));
				}
			sort(arr.begin(), arr.end());
			arr.erase(unique(arr.begin(), arr.end()), arr.end());
			sz = isz(arr);
			for (int j = 1; j <= sz; j++){
				node1[j].clear();
				node2[j].clear();
			}
			for (int j = 1; j <= num; j++){
				if (del[j]) continue;
				int x = lower_bound(arr.begin(), arr.end(), -(r[j]-l[j]+1))-arr.begin()+1;
				fake_update(node1, x, -l[j]);
				fake_update(node2, x, r[j]);
			}
			for (int j = 1; j <= sz; j++){
				sort(node1[j].begin(), node1[j].end());
				sort(node2[j].begin(), node2[j].end());
				bit1[j].assign(isz(node1[j])+1, 0);
				bit2[j].assign(isz(node2[j])+1, 0);
			}
			memset(cnt, 0, sizeof(cnt));
			for (int j = 1; j <= num; j++){
				if (del[j]) continue;
				int x = lower_bound(arr.begin(), arr.end(), -(r[j]-l[j]+1))-arr.begin()+1;
				update(node1, bit1, x, -l[j]);
				update(node2, bit2, x, r[j]);
				update_cnt(x);
			}
		}
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29020 KB Output is correct
2 Correct 9 ms 29176 KB Output is correct
3 Correct 16 ms 29300 KB Output is correct
4 Correct 16 ms 29512 KB Output is correct
5 Correct 19 ms 30808 KB Output is correct
6 Correct 20 ms 30556 KB Output is correct
7 Correct 18 ms 29528 KB Output is correct
8 Correct 20 ms 30300 KB Output is correct
9 Correct 21 ms 30040 KB Output is correct
10 Correct 19 ms 30556 KB Output is correct
11 Correct 22 ms 30044 KB Output is correct
12 Correct 21 ms 30048 KB Output is correct
13 Correct 20 ms 30428 KB Output is correct
14 Correct 20 ms 30040 KB Output is correct
15 Correct 16 ms 29532 KB Output is correct
16 Correct 16 ms 29532 KB Output is correct
17 Correct 19 ms 29820 KB Output is correct
18 Correct 19 ms 30552 KB Output is correct
19 Correct 20 ms 29788 KB Output is correct
20 Correct 19 ms 29788 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 32112 KB Output is correct
2 Correct 202 ms 32068 KB Output is correct
3 Correct 223 ms 32228 KB Output is correct
4 Correct 202 ms 31940 KB Output is correct
5 Execution timed out 5049 ms 58216 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 32084 KB Output is correct
2 Correct 183 ms 32084 KB Output is correct
3 Correct 190 ms 32156 KB Output is correct
4 Correct 192 ms 32348 KB Output is correct
5 Execution timed out 5006 ms 58524 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29020 KB Output is correct
2 Correct 9 ms 29176 KB Output is correct
3 Correct 16 ms 29300 KB Output is correct
4 Correct 16 ms 29512 KB Output is correct
5 Correct 19 ms 30808 KB Output is correct
6 Correct 20 ms 30556 KB Output is correct
7 Correct 18 ms 29528 KB Output is correct
8 Correct 20 ms 30300 KB Output is correct
9 Correct 21 ms 30040 KB Output is correct
10 Correct 19 ms 30556 KB Output is correct
11 Correct 22 ms 30044 KB Output is correct
12 Correct 21 ms 30048 KB Output is correct
13 Correct 20 ms 30428 KB Output is correct
14 Correct 20 ms 30040 KB Output is correct
15 Correct 16 ms 29532 KB Output is correct
16 Correct 16 ms 29532 KB Output is correct
17 Correct 19 ms 29820 KB Output is correct
18 Correct 19 ms 30552 KB Output is correct
19 Correct 20 ms 29788 KB Output is correct
20 Correct 19 ms 29788 KB Output is correct
21 Execution timed out 5046 ms 50036 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29020 KB Output is correct
2 Correct 9 ms 29176 KB Output is correct
3 Correct 16 ms 29300 KB Output is correct
4 Correct 16 ms 29512 KB Output is correct
5 Correct 19 ms 30808 KB Output is correct
6 Correct 20 ms 30556 KB Output is correct
7 Correct 18 ms 29528 KB Output is correct
8 Correct 20 ms 30300 KB Output is correct
9 Correct 21 ms 30040 KB Output is correct
10 Correct 19 ms 30556 KB Output is correct
11 Correct 22 ms 30044 KB Output is correct
12 Correct 21 ms 30048 KB Output is correct
13 Correct 20 ms 30428 KB Output is correct
14 Correct 20 ms 30040 KB Output is correct
15 Correct 16 ms 29532 KB Output is correct
16 Correct 16 ms 29532 KB Output is correct
17 Correct 19 ms 29820 KB Output is correct
18 Correct 19 ms 30552 KB Output is correct
19 Correct 20 ms 29788 KB Output is correct
20 Correct 19 ms 29788 KB Output is correct
21 Execution timed out 5046 ms 50036 KB Time limit exceeded
22 Halted 0 ms 0 KB -