Submission #768438

#	Time	Username	Problem	Language	Result	Execution time	Memory
768438		minhcool	Sweeping (JOI20_sweeping)	C++17	1 / 100	18096 ms	987948 KiB

sweeping

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1500005 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n, m, q;
int x[N], y[N];
int type[N], width[N];
 
ii answer[N];
 
vector<ii> asks[N];// ask which node, after which query?
 
vector<int> queries[N];// queries like "we start from query i, we ask for this node"
 
set<int> IT1[(2LL << 21)], IT2[(2LL << 21)];
 
void upd1(int id, int l, int r, int pos, int val, bool add){
	if(add) IT1[id].insert(val);
	else IT1[id].erase(val);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd1(id << 1, l, mid, pos, val, add);
	else upd1(id << 1 | 1, mid + 1, r, pos, val, add);
}
 
int get1(int id, int l, int r, int le, int ri){
	if(IT1[id].size() == 0) return oo;
	if(l == r){
		int temp = (*IT1[id].begin());
		if(temp > ri || temp < le) return oo;
		return l;
	}
//	cout << "ID " << id << " ";
//	for(auto it : IT1[id]) cout << it << " ";
//	cout << "\n";
	int mid = (l + r) >> 1;
	if(!IT1[id << 1].size()) return get1(id << 1 | 1, mid + 1, r, le, ri);
	else{
		set<int>::iterator it = IT1[id << 1].lower_bound(le);
		if(it == IT1[id << 1].end() || (*it) > ri) return get1(id << 1 | 1, mid + 1, r, le, ri);
		else return get1(id << 1, l, mid, le, ri);
	}
}
 
void upd2(int id, int l, int r, int pos, int val, bool add){
	if(add) IT2[id].insert(val);
	else IT2[id].erase(val);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd2(id << 1, l, mid, pos, val, add);
	else upd2(id << 1 | 1, mid + 1, r, pos, val, add);
}
 
int get2(int id, int l, int r, int le, int ri){
	if(IT2[id].size() == 0) return oo;
	if(l == r){
		int temp = (*IT2[id].begin());
		if(temp > ri || temp < le) return oo;
		return l;
	}
	int mid = (l + r) >> 1;
	if(!IT2[id << 1].size()) return get2(id << 1 | 1, mid + 1, r, le, ri);
	else{
		set<int>::iterator it = IT2[id << 1].lower_bound(le);
		if(it == IT2[id << 1].end() || (*it) > ri) return get2(id << 1 | 1, mid + 1, r, le, ri);
		else return get2(id << 1, l, mid, le, ri);
	}
}
 
vector<int> v1, v2;
 
#ifdef local
void process(){
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++){
		cin >> x[i] >> y[i];
		queries[1].pb(i);
	} 
	int cnt1 = m, cnt2 = 0, cnt3 = 0;
	for(int i = 1; i <= q; i++){
		int typ;
		cin >> typ;
		if(typ == 1){
			int x;
			cin >> x;
			cnt3++;
			asks[x].pb({cnt2, cnt3});
		}
		else if(typ == 2){
			cnt2++;	
			int l;
			cin >> l;
			type[cnt2] = 0, width[cnt2] = l;
		}
		else if(typ == 3){
			cnt2++;
			int l;
			cin >> l;
			type[cnt2] = 1, width[cnt2] = l;
		}
		else{
			cnt1++;
			cin >> x[cnt1] >> y[cnt1];
			queries[cnt2 + 1].pb(cnt1);
		}
	}
	for(int i = 1; i <= cnt1; i++) reverse(asks[i].begin(), asks[i].end());
	int cnth = 0, cntv = 0;
	for(int i = 1; i <= cnt2; i++){
		if(type[i] == 0) cnth++;
		else cntv++;
	}
	int temph = cnth, tempv = cntv;
	cnth = 0, cntv = 0;
	v1.pb(-1), v2.pb(-1);
	for(int i = 1; i <= cnt2; i++){
		if(type[i] == 0){
			cnth++;
		//	cout << "OKOKOK " << width[i] << "\n";
			upd1(1, 1, temph, cnth, width[i], 1);
			v1.pb(i);
		}
		else{
			cntv++;
			upd2(1, 1, tempv, cntv, width[i], 1);
			v2.pb(i);
		}
	}
	v1.pb(oo), v2.pb(oo);
	//return;
	cnth = 0, cntv = 0;
	for(int i = 1; i <= cnt2; i++){
		for(auto it : queries[i]){
			int pos = it, pos1 = oo, pos2 = oo;
			// H first: given current (x, y)
			int le = y[pos], ri = n - x[pos] - 1;
			if(le <= ri) pos1 = get1(1, 1, temph, le, ri);
		//	cout << le << " " << ri << "\n";
			le = x[pos], ri = n - y[pos] - 1;
			if(le <= ri) pos2 = get2(1, 1, tempv, le, ri);
		//	cout << le << " " << ri << "\n";
		//	continue;
			pos1 = v1[min((int)v1.size() - 1, pos1)], pos2 = v2[min((int)v2.size() - 1, pos2)];
		//	cout << i << " " << pos << " " << pos1 << " " << pos2 << "\n";
			while(asks[pos].size() && asks[pos].back().fi < min(pos1, pos2)){
		//		cout << "OK " << asks[pos].back().fi << " " << asks[pos].back().se << "\n";
				answer[asks[pos].back().se] = make_pair(x[pos], y[pos]);
				asks[pos].pop_back();
			}
			if(min(pos1, pos2) > cnt2) continue;
		//	cout << pos1 << " " << pos2 << "\n";
		//	continue;
			if(pos1 < pos2) x[pos] = n - width[pos1];
			else y[pos] = n - width[pos2];
		//	cout << pos1 << " " << pos2 << "\n";
		//	continue;
			queries[min(pos1, pos2) + 1].pb(it);
		}
		if(type[i] == 0){
			cnth++;
			upd1(1, 1, temph, cnth, width[i], 0);
		}
		else{
			cntv++;
			upd2(1, 1, tempv, cntv, width[i], 0);
		}
	}
	for(int i = 1; i <= cnt1; i++){
		for(auto it : asks[i]) answer[it.se] = {x[i], y[i]};
	}
	for(int i = 1; i <= cnt3; i++) cout << answer[i].fi << " " << answer[i].se << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("sweep.inp", "r", stdin);
	//freopen("sweep.out", "w", stdout);
	cin.tie(0);
	process();
}
#endif

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