Submission #1047915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047915		flappybird	Sweeping (JOI20_sweeping)	C++17	22 / 100	3890 ms	489352 KiB

sweeping

//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2010101
#define MAXQ 101010
#define INF 1'000'000'100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
#ifdef LOCAL
#define DEBUG(a) cout<<a
#define TEST true
#else
#define DEBUG(...) 1234
#define TEST false
#endif

int N, M, Q;

//points
int X[MAX];
int Y[MAX];
int S[MAX];
vector<int> es[MAX];
//queries
int T[MAX];
int L[MAX];
pii ans[MAX];
vector<int> qv[MAX];

struct node {
	int val;
	int key;
	int p, n;
	int lnk;
	node(int k = 0, int v = 0, int p = 0, int n = 0) :p(p), n(n) {
		val = v;
		key = k;
		lnk = 0;
	}
};

vector<node> MEM;

void disc(int n) {
	if (MEM[n].p) MEM[MEM[n].p].n = MEM[n].n;
	if (MEM[n].n) MEM[MEM[n].n].p = MEM[n].p;
	MEM[n].p = MEM[n].n = 0;
}

int make_node(int k, int v, int p = 0, int n = 0) {
	int s = MEM.size();
	MEM.push_back(node(k, v, p, n));
	return s;
}

struct Dat {
	int sv[2] = { 0, 0 }; //linked list
	int ev[2] = { 0, 0 };
	int cap[2] = { 0, 0 }; //cap from down
	int N;
	void init(vector<int> K, vector<vector<int>> X) {
		vector<pii> ord;
		N = K.size();
		int i;
		for (i = 0; i < N; i++) ord.emplace_back(i, 0);

		sort(ord.begin(), ord.end(), [&](pii i, pii j) {return X[0][i.first] < X[0][j.first]; });
		int pv = 0;
		for (auto& v : ord) {
			int nn = make_node(K[v.first], X[0][v.first], pv);
			if (!sv[0]) sv[0] = nn;
			ev[0] = nn;
			v.second = nn;
			if (pv) MEM[pv].n = nn;
			pv = nn;
		}

		sort(ord.begin(), ord.end(), [&](pii i, pii j) {return X[1][i.first] < X[1][j.first]; });
		pv = 0;
		for (auto& v : ord) {
			int nn = make_node(K[v.first], X[1][v.first], pv);
			if (!sv[1]) sv[1] = nn;
			ev[1] = nn;
			if (pv) MEM[pv].n = nn;
			MEM[nn].lnk = v.second;
			MEM[v.second].lnk = nn;
			pv = nn;
		}
	}

	int& begin(int c) { return sv[c]; }
	int& rbegin(int c) { return ev[c]; }
	node& front(int c) { return MEM[sv[c]]; }
	node& back(int c) { return MEM[ev[c]]; }
};

vector<Dat> lists;
int flag; // flag for divide function

int divide(Dat& D, int c, int L) {
	int op = c ^ 1;
	int n = D.N;
	if (max(D.cap[c], D.front(c).val) >= L) {
		flag = 0;
		return -1;
	}
	if (max(D.cap[c], D.back(c).val) < L) {
		flag = 1;
		return -1;
	}
	int i;
	int chk = 0;
	int rem = 0; // remove
	int s, e;
	s = D.begin(c);
	e = D.rbegin(c);
	for (i = 0; i < n; i++) {
		if (max(D.cap[c], MEM[s].val) >= L) {
			chk = 0;
			rem = i;
			break;
		}
		if (max(D.cap[c], MEM[e].val) < L) {
			chk = 1;
			rem = i;
			break;
		}
		s = MEM[s].n;
		e = MEM[e].p;
	}
	Dat nd;
	nd.cap[0] = D.cap[0];
	nd.cap[1] = D.cap[1];
	s = D.begin(c);
	e = D.rbegin(c);
	nd.N = rem;
	if (chk) { //remove from back
		e = D.rbegin(c);
		vector<int> rems;
		for (i = 0; i < rem; i++) {
			int opn = MEM[e].lnk;
			assert(opn);
			assert(e);
			if (opn == D.begin(op)) D.begin(op) = MEM[opn].n;
			if (opn == D.rbegin(op)) D.rbegin(op) = MEM[opn].p;
			disc(opn);
			rems.push_back(opn);
			e = MEM[e].p;
		}
		int ns = MEM[e].n; // [list 1(original)] ... e / ns ... [list 2(new)]
		MEM[e].n = 0;
		MEM[ns].p = 0;

		// D.sv[op], D.ev[op] is correct

		sort(rems.begin(), rems.end());
		for (i = 1; i < rem; i++) {
			MEM[rems[i - 1]].n = rems[i];
			MEM[rems[i]].p = rems[i - 1];
			assert(MEM[rems[i - 1]].val <= MEM[rems[i]].val);
		}

		nd.sv[c] = ns;
		nd.sv[op] = rems[0];
		nd.ev[c] = D.ev[c];
		nd.ev[op] = rems.back();

		D.ev[c] = e;
		flag = 0;
	}
	else { // remove from front
		s = D.begin(c);
		vector<int> rems;
		for (i = 0; i < rem; i++) {
			int opn = MEM[s].lnk;
			assert(opn);
			assert(e);
			if (opn == D.begin(op)) D.begin(op) = MEM[opn].n;
			if (opn == D.rbegin(op)) D.rbegin(op) = MEM[opn].p;
			disc(opn);
			rems.push_back(opn);
			s = MEM[s].n;
		}
		int ne = MEM[s].p; // [list 1(new)] ... ne / s ... [list 2(original)]
		MEM[s].p = 0;
		MEM[ne].n = 0;

		// D.sv[op], D.ev[op] is correct

		sort(rems.begin(), rems.end());
		for (i = 1; i < rem; i++) {
			MEM[rems[i - 1]].n = rems[i];
			MEM[rems[i]].p = rems[i - 1];
		}

		nd.sv[c] = D.sv[c];
		nd.sv[op] = rems[0];
		nd.ev[c] = ne;
		nd.ev[op] = rems.back();

		D.sv[c] = s;
		flag = 1;
	}
	D.N = n - rem;
	lists.push_back(nd);
	return lists.size() - 1;
}

void solve(int l, int r, vector<int>& v) {
	lists.clear();
	MEM.clear();
	MEM.push_back(node());
	int i;
	int n = v.size();
	vector<int> K(n);
	vector<vector<int>> val(2, vector<int>(K.size()));
	for (i = 0; i < n; i++) {
		K[i] = v[i];
		val[0][i] = X[v[i]];
		val[1][i] = Y[v[i]];
	}
	Dat d;
	d.init(K, val);
	lists.push_back(d);
	set<pii> st; // (left top point of the triangle, index in lists)
	st.emplace(-2, 0);
	for (i = l; i <= r; i++) {
		if (T[i] == 1 || T[i] == 4) continue;
		if (T[i] == 2) {
			int v = N - L[i];
			auto it = st.lower_bound(pii(v, 0));
			it--;
			int pv = it->first;
			int ind1 = it->second;
			st.erase(it);
			int ind2 = divide(lists[ind1], 1, L[i] + 1);

			if (!~ind2) {
				if (flag) lists[ind1].cap[0] = max(lists[ind1].cap[0], v);
				st.emplace(pv, ind1);
				continue;
			}

			if (flag) { //reversed
				st.emplace(pv, ind1);
				st.emplace(v, ind2);
				lists[ind2].cap[0] = max(lists[ind2].cap[0], v);
			}
			else {
				st.emplace(pv, ind2);
				st.emplace(v, ind1);
				lists[ind1].cap[0] = max(lists[ind1].cap[0], v);
			}
		}
		else {
			int v = N - L[i];
			auto it = st.lower_bound(pii(L[i] + 1, 0));
			it--;
			int pv = it->first;
			int ind1 = it->second;
			st.erase(it);
			int ind2 = divide(lists[ind1], 0, L[i] + 1);

			if (!~ind2) {
				if (flag) lists[ind1].cap[1] = max(lists[ind1].cap[1], v);
				st.emplace(pv, ind1);
				continue;
			}

			if (flag) { //reversed
				st.emplace(pv, ind2);
				st.emplace(L[i], ind1);
				lists[ind2].cap[1] = max(lists[ind2].cap[1], v);
			}
			else {
				st.emplace(pv, ind1);
				st.emplace(L[i], ind2);
				lists[ind1].cap[1] = max(lists[ind1].cap[1], v);
			}
		}
	}
	for (auto& d : lists) {
		assert(!MEM[d.sv[0]].p);
		assert(!MEM[d.sv[1]].p);
		assert(!MEM[d.ev[0]].n);
		assert(!MEM[d.ev[1]].n);
		int s = d.sv[0];
		for (i = 0; i < d.N; i++) {
			int v = MEM[s].key;
			X[v] = max(X[v], d.cap[0]);
			Y[v] = max(Y[v], d.cap[1]);
			if (qv[v].size() && qv[v].back() == r) {
				ans[qv[v].back()] = pii(X[v], Y[v]);
				qv[v].pop_back();
			}
			s = MEM[s].n;
		}
	}
}

vector<int> tree[MAX * 4];
vector<tuple<int, int, int>> vt;

void init(int s, int e, int loc = 1) {
	vt.emplace_back(s, e, loc);
	if (s == e) return;
	int m = s + e >> 1;
	init(s, m, loc * 2);
	init(m + 1, e, loc * 2 + 1);
}

void add(int s, int e, int l, int r, int v, int loc = 1) {
	if (e < l || r < s) return;
	if (l <= s && e <= r) {
		tree[loc].push_back(v);
		return;
	}
	int m = s + e >> 1;
	add(s, m, l, r, v, loc * 2);
	add(m + 1, e, l, r, v, loc * 2 + 1);
}
#ifdef LOCAL
#define cin fin
ifstream fin("C:\\Users\\flapp\\Downloads\\sweeping-data\\in\\04-10.txt");
#endif

signed main() {
#ifndef LOCAL
	ios::sync_with_stdio(false), cin.tie(0);
#endif
	cin >> N >> M >> Q;
	int i, x;
	for (i = 1; i <= M; i++) {
		cin >> X[i] >> Y[i];
		S[i] = 1;
	}
	init(1, Q);
	for (i = 1; i <= Q; i++) {
		cin >> T[i];
		if (T[i] == 1) {
			cin >> x;
			if (qv[x].empty()) add(1, Q, S[x], i, x);
			else add(1, Q, qv[x].back() + 1, i, x);
			qv[x].push_back(i);
		}
		if (T[i] == 2 || T[i] == 3) cin >> L[i];
		if (T[i] == 4) {
			S[++M] = i;
			cin >> X[M] >> Y[M];
		}
	}
	for (i = 1; i <= M; i++) reverse(qv[i].begin(), qv[i].end());
	sort(vt.begin(), vt.end());
	for (auto& [l, r, v] : vt) if (tree[v].size()) solve(l, r, tree[v]);
	for (i = 1; i <= Q; i++) if (T[i] == 1) cout << ans[i].first << bb << ans[i].second << ln;
}

Compilation message (stderr)

sweeping.cpp: In function 'void init(int, int, int)':
sweeping.cpp:318:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  318 |  int m = s + e >> 1;
      |          ~~^~~
sweeping.cpp: In function 'void add(int, int, int, int, int, int)':
sweeping.cpp:329:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  329 |  int m = s + e >> 1;
      |          ~~^~~

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