Submission #258873

#	Time	Username	Problem	Language	Result	Execution time	Memory
258873		Saboon	Sweeping (JOI20_sweeping)	C++14	0 / 100	2308 ms	55572 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;

const int maxn = 5e5 + 10;

int x[maxn], y[maxn];
int seg[4*maxn][3], lazy[4*maxn][3];

void shift(int);

int bs2(int id, int L, int R, int val){
	if (L + 1 == R)
		return L;
	shift(id);
	int mid = (L + R) >> 1;
	if (seg[2*id+1][2] < val)
		return bs2(2*id+1, mid, R, val);
	return bs2(2*id+0, L, mid, val);
}

int bs1(int id, int L, int R, int val){
	if (L + 1 == R)
		return L;
	shift(id);
	int mid = (L + R) >> 1;
	if (seg[2*id+0][1] > val)
		return bs1(2*id+0, L, mid, val);
	return bs1(2*id+1, mid, R, val);
}

int get(int id, int L, int R, int idx, int w){
	if (L + 1 == R)
		return seg[id][w];
	shift(id);
	int mid = (L + R) >> 1;
	if (idx < mid)
		return get(2*id+0, L, mid, idx, w);
	return get(2*id+1, mid, R, idx, w);
}

void change(int id, int L, int R, int l, int r, int val, int w){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		seg[id][w] = val;
		lazy[id][w] = val;
		return;
	}
	shift(id);
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, l, r, val, w);
	change(2*id+1, mid, R, l, r, val, w);
	seg[id][1] = max(seg[2*id+0][1], seg[2*id+1][1]);
	seg[id][2] = min(seg[2*id+0][2], seg[2*id+1][2]);
}

void shift(int id){
	for (int i = 1; i <= 2; i++){
		if (lazy[id][i] != 0){
			change(2*id+0, 0, 1, 0, 1, lazy[id][i], i);
			change(2*id+1, 0, 1, 0, 1, lazy[id][i], i);
			lazy[id][i] = 0;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++)
		cin >> x[i] >> y[i];
	y[0] = n+1, x[0] = -1, x[m+1] = n+1, y[m+1] = -1;
	m += 2;
	for (int i = 0; i < m; i++){
		change(1, 0, m, i, i+1, x[i], 1);
		change(1, 0, m, i, i+1, y[i], 2);
	}
	while (q --){
		int type;
		cin >> type;
		if (type == 1){
			int idx;
			cin >> idx;
			cout << get(1, 0, m, idx, 1) << " " << get(1, 0, m, idx, 2) << '\n';
		}
		else if (type == 2){
			int w;
			cin >> w;
			int l = bs2(1, 0, m, w), r = bs1(1, 0, m, n-w);
			change(1, 0, m, l, r, n-w, 1);
		}
		else{
			int w;
			cin >> w;
			int l = bs2(1, 0, m, n-w), r = bs1(1, 0, m, w);
			change(1, 0, m, l, r, n-w, 2);
		}
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25