oj.uz

Submission #908511

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

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

const int NM = 2e5, BL = 4000, 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 7 ms 23036 KB Output is correct
2 Correct 7 ms 22872 KB Output is correct
3 Correct 21 ms 23256 KB Output is correct
4 Correct 21 ms 23064 KB Output is correct
5 Correct 18 ms 23900 KB Output is correct
6 Correct 22 ms 23900 KB Output is correct
7 Correct 24 ms 23332 KB Output is correct
8 Correct 20 ms 23644 KB Output is correct
9 Correct 22 ms 23632 KB Output is correct
10 Correct 14 ms 23900 KB Output is correct
11 Correct 30 ms 23556 KB Output is correct
12 Correct 29 ms 23636 KB Output is correct
13 Correct 16 ms 23900 KB Output is correct
14 Correct 23 ms 23644 KB Output is correct
15 Correct 20 ms 23132 KB Output is correct
16 Correct 24 ms 23132 KB Output is correct
17 Correct 22 ms 23320 KB Output is correct
18 Correct 15 ms 23900 KB Output is correct
19 Correct 22 ms 23384 KB Output is correct
20 Correct 25 ms 23384 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2571 ms 35396 KB Output is correct
2 Correct 2549 ms 35200 KB Output is correct
3 Correct 2636 ms 35324 KB Output is correct
4 Correct 2911 ms 38700 KB Output is correct
5 Runtime error 4086 ms 48504 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 24136 KB Output is correct
2 Correct 357 ms 24168 KB Output is correct
3 Correct 359 ms 23932 KB Output is correct
4 Correct 368 ms 24328 KB Output is correct
5 Runtime error 3875 ms 42124 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23036 KB Output is correct
2 Correct 7 ms 22872 KB Output is correct
3 Correct 21 ms 23256 KB Output is correct
4 Correct 21 ms 23064 KB Output is correct
5 Correct 18 ms 23900 KB Output is correct
6 Correct 22 ms 23900 KB Output is correct
7 Correct 24 ms 23332 KB Output is correct
8 Correct 20 ms 23644 KB Output is correct
9 Correct 22 ms 23632 KB Output is correct
10 Correct 14 ms 23900 KB Output is correct
11 Correct 30 ms 23556 KB Output is correct
12 Correct 29 ms 23636 KB Output is correct
13 Correct 16 ms 23900 KB Output is correct
14 Correct 23 ms 23644 KB Output is correct
15 Correct 20 ms 23132 KB Output is correct
16 Correct 24 ms 23132 KB Output is correct
17 Correct 22 ms 23320 KB Output is correct
18 Correct 15 ms 23900 KB Output is correct
19 Correct 22 ms 23384 KB Output is correct
20 Correct 25 ms 23384 KB Output is correct
21 Correct 2571 ms 35396 KB Output is correct
22 Correct 2549 ms 35200 KB Output is correct
23 Correct 2636 ms 35324 KB Output is correct
24 Correct 2911 ms 38700 KB Output is correct
25 Runtime error 4086 ms 48504 KB Memory limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23036 KB Output is correct
2 Correct 7 ms 22872 KB Output is correct
3 Correct 21 ms 23256 KB Output is correct
4 Correct 21 ms 23064 KB Output is correct
5 Correct 18 ms 23900 KB Output is correct
6 Correct 22 ms 23900 KB Output is correct
7 Correct 24 ms 23332 KB Output is correct
8 Correct 20 ms 23644 KB Output is correct
9 Correct 22 ms 23632 KB Output is correct
10 Correct 14 ms 23900 KB Output is correct
11 Correct 30 ms 23556 KB Output is correct
12 Correct 29 ms 23636 KB Output is correct
13 Correct 16 ms 23900 KB Output is correct
14 Correct 23 ms 23644 KB Output is correct
15 Correct 20 ms 23132 KB Output is correct
16 Correct 24 ms 23132 KB Output is correct
17 Correct 22 ms 23320 KB Output is correct
18 Correct 15 ms 23900 KB Output is correct
19 Correct 22 ms 23384 KB Output is correct
20 Correct 25 ms 23384 KB Output is correct
21 Correct 2571 ms 35396 KB Output is correct
22 Correct 2549 ms 35200 KB Output is correct
23 Correct 2636 ms 35324 KB Output is correct
24 Correct 2911 ms 38700 KB Output is correct
25 Runtime error 4086 ms 48504 KB Memory limit exceeded
26 Halted 0 ms 0 KB -