oj.uz

답안 #908520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908520 2024-01-16T13:24:13 Z daoquanglinh2007 Segments (IZhO18_segments) C++17
7 / 100
 1642 ms 39716 KB 
#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 <short> 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 <short> 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 <short> 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 31 ms 22876 KB Output is correct
4 Correct 30 ms 22876 KB Output is correct
5 Correct 23 ms 22872 KB Output is correct
6 Correct 30 ms 23036 KB Output is correct
7 Correct 33 ms 23072 KB Output is correct
8 Correct 21 ms 22876 KB Output is correct
9 Correct 22 ms 22876 KB Output is correct
10 Correct 12 ms 22876 KB Output is correct
11 Correct 33 ms 22872 KB Output is correct
12 Correct 35 ms 22876 KB Output is correct
13 Correct 12 ms 22872 KB Output is correct
14 Correct 22 ms 23068 KB Output is correct
15 Correct 29 ms 22876 KB Output is correct
16 Correct 30 ms 22876 KB Output is correct
17 Correct 26 ms 22876 KB Output is correct
18 Correct 16 ms 23056 KB Output is correct
19 Correct 27 ms 22992 KB Output is correct
20 Correct 30 ms 23320 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1174 ms 33928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1195 ms 24280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1070 ms 24012 KB Output is correct
2 Correct 1076 ms 24236 KB Output is correct
3 Correct 1072 ms 24060 KB Output is correct
4 Correct 1082 ms 24120 KB Output is correct
5 Incorrect 1642 ms 39716 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 31 ms 22876 KB Output is correct
4 Correct 30 ms 22876 KB Output is correct
5 Correct 23 ms 22872 KB Output is correct
6 Correct 30 ms 23036 KB Output is correct
7 Correct 33 ms 23072 KB Output is correct
8 Correct 21 ms 22876 KB Output is correct
9 Correct 22 ms 22876 KB Output is correct
10 Correct 12 ms 22876 KB Output is correct
11 Correct 33 ms 22872 KB Output is correct
12 Correct 35 ms 22876 KB Output is correct
13 Correct 12 ms 22872 KB Output is correct
14 Correct 22 ms 23068 KB Output is correct
15 Correct 29 ms 22876 KB Output is correct
16 Correct 30 ms 22876 KB Output is correct
17 Correct 26 ms 22876 KB Output is correct
18 Correct 16 ms 23056 KB Output is correct
19 Correct 27 ms 22992 KB Output is correct
20 Correct 30 ms 23320 KB Output is correct
21 Incorrect 1174 ms 33928 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22876 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 31 ms 22876 KB Output is correct
4 Correct 30 ms 22876 KB Output is correct
5 Correct 23 ms 22872 KB Output is correct
6 Correct 30 ms 23036 KB Output is correct
7 Correct 33 ms 23072 KB Output is correct
8 Correct 21 ms 22876 KB Output is correct
9 Correct 22 ms 22876 KB Output is correct
10 Correct 12 ms 22876 KB Output is correct
11 Correct 33 ms 22872 KB Output is correct
12 Correct 35 ms 22876 KB Output is correct
13 Correct 12 ms 22872 KB Output is correct
14 Correct 22 ms 23068 KB Output is correct
15 Correct 29 ms 22876 KB Output is correct
16 Correct 30 ms 22876 KB Output is correct
17 Correct 26 ms 22876 KB Output is correct
18 Correct 16 ms 23056 KB Output is correct
19 Correct 27 ms 22992 KB Output is correct
20 Correct 30 ms 23320 KB Output is correct
21 Incorrect 1174 ms 33928 KB Output isn't correct
22 Halted 0 ms 0 KB -