oj.uz

Submission #908524

# Submission time Handle Problem Language Result Execution time Memory
908524 2024-01-16T13:30:32 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
7 / 100
 1708 ms 44848 KB 
#pragma GCC optimize("conserve-stack")

#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
 
const int NM = 2e5, BL = 10000, inf = INT_MAX;
 
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];
vector <int> 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 find_pos_ll(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_ll(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;
}
 
int 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] < +inf-(k[i]-2) ? a[i]+k[i]-2 : +inf));
			          
			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 22876 KB Output is correct
2 Correct 8 ms 23028 KB Output is correct
3 Correct 34 ms 22876 KB Output is correct
4 Correct 31 ms 22872 KB Output is correct
5 Correct 24 ms 22876 KB Output is correct
6 Correct 30 ms 22872 KB Output is correct
7 Correct 30 ms 22980 KB Output is correct
8 Correct 21 ms 22876 KB Output is correct
9 Correct 25 ms 23060 KB Output is correct
10 Correct 13 ms 23040 KB Output is correct
11 Correct 36 ms 23128 KB Output is correct
12 Correct 38 ms 23052 KB Output is correct
13 Correct 12 ms 22876 KB Output is correct
14 Correct 24 ms 22876 KB Output is correct
15 Correct 31 ms 22876 KB Output is correct
16 Correct 31 ms 22876 KB Output is correct
17 Correct 27 ms 22872 KB Output is correct
18 Correct 16 ms 22872 KB Output is correct
19 Correct 35 ms 23052 KB Output is correct
20 Correct 28 ms 22876 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 35372 KB Output is correct
2 Correct 1489 ms 35184 KB Output is correct
3 Correct 1328 ms 35340 KB Output is correct
4 Correct 1420 ms 36088 KB Output is correct
5 Runtime error 1708 ms 44848 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1174 ms 24372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1088 ms 24224 KB Output is correct
2 Correct 1052 ms 24112 KB Output is correct
3 Correct 1087 ms 24124 KB Output is correct
4 Correct 1116 ms 24164 KB Output is correct
5 Runtime error 1693 ms 41884 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 22876 KB Output is correct
2 Correct 8 ms 23028 KB Output is correct
3 Correct 34 ms 22876 KB Output is correct
4 Correct 31 ms 22872 KB Output is correct
5 Correct 24 ms 22876 KB Output is correct
6 Correct 30 ms 22872 KB Output is correct
7 Correct 30 ms 22980 KB Output is correct
8 Correct 21 ms 22876 KB Output is correct
9 Correct 25 ms 23060 KB Output is correct
10 Correct 13 ms 23040 KB Output is correct
11 Correct 36 ms 23128 KB Output is correct
12 Correct 38 ms 23052 KB Output is correct
13 Correct 12 ms 22876 KB Output is correct
14 Correct 24 ms 22876 KB Output is correct
15 Correct 31 ms 22876 KB Output is correct
16 Correct 31 ms 22876 KB Output is correct
17 Correct 27 ms 22872 KB Output is correct
18 Correct 16 ms 22872 KB Output is correct
19 Correct 35 ms 23052 KB Output is correct
20 Correct 28 ms 22876 KB Output is correct
21 Correct 1504 ms 35372 KB Output is correct
22 Correct 1489 ms 35184 KB Output is correct
23 Correct 1328 ms 35340 KB Output is correct
24 Correct 1420 ms 36088 KB Output is correct
25 Runtime error 1708 ms 44848 KB Memory limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 22876 KB Output is correct
2 Correct 8 ms 23028 KB Output is correct
3 Correct 34 ms 22876 KB Output is correct
4 Correct 31 ms 22872 KB Output is correct
5 Correct 24 ms 22876 KB Output is correct
6 Correct 30 ms 22872 KB Output is correct
7 Correct 30 ms 22980 KB Output is correct
8 Correct 21 ms 22876 KB Output is correct
9 Correct 25 ms 23060 KB Output is correct
10 Correct 13 ms 23040 KB Output is correct
11 Correct 36 ms 23128 KB Output is correct
12 Correct 38 ms 23052 KB Output is correct
13 Correct 12 ms 22876 KB Output is correct
14 Correct 24 ms 22876 KB Output is correct
15 Correct 31 ms 22876 KB Output is correct
16 Correct 31 ms 22876 KB Output is correct
17 Correct 27 ms 22872 KB Output is correct
18 Correct 16 ms 22872 KB Output is correct
19 Correct 35 ms 23052 KB Output is correct
20 Correct 28 ms 22876 KB Output is correct
21 Correct 1504 ms 35372 KB Output is correct
22 Correct 1489 ms 35184 KB Output is correct
23 Correct 1328 ms 35340 KB Output is correct
24 Correct 1420 ms 36088 KB Output is correct
25 Runtime error 1708 ms 44848 KB Memory limit exceeded
26 Halted 0 ms 0 KB -