Submission #563590

#	Time	Username	Problem	Language	Result	Execution time	Memory
563590		ngpin04	Sweeping (JOI20_sweeping)	C++14	0 / 100	1046 ms	770252 KiB

sweeping

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 2e6 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct trie {
	struct node {
		int cnt;
		int ptr[2];
		node(int _cnt = 0) {
			cnt = _cnt;
			for (int i = 0; i < 2; i++)
				ptr[i] = 0;
		}
	};

	vector <node> tree;
	int node,sz;

	#define ptr(cur, i) tree[cur].ptr[i]
	#define cnt(cur) tree[cur].cnt

	trie() {
		node = 0;
		sz = 0;
		tree.emplace_back();
	}

	void add(int x, int val) {
		sz += val;
		int cur = 0;
		for (int i = 29; i >= 0; i--) {
			int v = getbit(x, i);
			if (ptr(cur, v)) {
				ptr(cur, v) = ++node;
				tree.emplace_back();
			}
			cur = ptr(cur, v);
			cnt(cur)++;
		}
	}

	int getcnt(int x) {
		int cur = 0;
		int res = 0;
		for (int i = 29; i >= 0; i--) {
			int v = getbit(x, i);
			for (int j = 0; j < v; j++)
				res += cnt(ptr(cur, 0));
			cur = ptr(cur, 1);
		}		
		return res;
	}
};

vector <trie> tx, ty;

map <int, int> posx;

set <pair <int, int>> sx[N], sy[N];

trie block[N];

int curx[N];
int cury[N];
int ind[N];
int bk[N];
int op[N];
int x[N];
int y[N];
int n,m,q,nDust,nBlock;

void change(int i, int newb) {
	int curb = bk[i];
	tx[curb].add(x[i], -1);
	ty[curb].add(y[i], -1);
	sx[curb].erase(mp(x[i], i));
	sy[curb].erase(mp(y[i], i));

	bk[i] = newb;

	tx[newb].add(x[i], 1);
	ty[newb].add(y[i], 1);
	sx[newb].insert(mp(x[i], i));
	sy[newb].insert(mp(y[i], i));	
}

void sub1() {
	posx[0] = 0;
	tx.emplace_back(), ty.emplace_back();
	for (int i = 1; i <= m; i++) {
		sx[0].insert(mp(x[i], i));
		sy[0].insert(mp(y[i], i));
		tx[0].add(x[i], 1);
		ty[0].add(y[i], 1);
		bk[i] = 0;
	}

	for (int i = m + 1; i <= q; i++) {
		if (op[i] == 1) {
			int id = ind[i];
			cout << max(curx[bk[id]], x[id]) 
			<< " " << max(cury[bk[id]], y[id]) << "\n";
		} else if (op[i] == 2) {
			int Lx = n - x[i];
			int Ly = x[i];	
			// cerr << i << " " << Lx << " " << Ly << "\n";	
			if (posx.count(Lx) == 0) {
				int pre = prev(posx.lower_bound(Lx))->se;
				int up = ty[pre].getcnt(Ly + 1);
				int dn = ty[pre].sz - up;

				posx[Lx] = ++nBlock;
				curx[nBlock] = Lx;
				tx.emplace_back();
				ty.emplace_back();

				int cur = nBlock;
				if (up < dn) {
					while (sy[pre].size()) {
						auto it = prev(sy[pre].end());
						if (y[it->se] <= Ly) 
							break;
						change(it->se, cur);
					}	

					swap(sx[pre], sx[cur]);
					swap(sy[pre], sy[cur]);
					swap(tx[pre], tx[cur]);
					swap(ty[pre], ty[cur]);
				} else {
					while (sy[pre].size()) {
						auto it = sy[pre].begin();
						if (y[it->se] > Ly)
							break;
						change(it->se, cur);
					}
				}
			}
		} else {
			int Lx = x[i];
			int Ly = n - x[i];
			int pre = prev(posx.lower_bound(Lx))->se;
			int lf = tx[pre].getcnt(Lx + 1);
			int rt = tx[pre].sz - lf;

			posx[Lx] = ++nBlock;
			curx[nBlock] = Lx;

			int cur = nBlock;
			if (lf > rt) {
				while (sx[pre].size()) {
					auto it = prev(sx[pre].end());
					if (x[it->se] <= Lx) 
						break;
					change(it->se, cur);
				}	
			} else {
				while (sx[pre].size()) {
					auto it = sx[pre].begin();
					if (x[it->se] > Lx)
						break;
					change(it->se, cur);
				}

				swap(sx[pre], sx[cur]);
				swap(sy[pre], sy[cur]);
				swap(tx[pre], tx[cur]);
				swap(ty[pre], ty[cur]);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		op[i] = 4;
		cin >> x[i] >> y[i];
	}	

	q += m;
	for (int i = m + 1; i <= q; i++) {
		cin >> op[i];
		assert(op[i] <= 3);
		if (op[i] == 1) {
			cin >> ind[i];
		} else if (op[i] <= 3) {
			cin >> x[i];
		} else 
			cin >> x[i] >> y[i];
	}

	sub1();
	
	return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'void sub1()':
sweeping.cpp:163:8: warning: unused variable 'Ly' [-Wunused-variable]
  163 |    int Ly = n - x[i];
      |        ^~

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