Submission #1262772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262772		flappybird	Card Collection (JOI24_collection)	C++20	0 / 100	37 ms	78916 KiB

Main

#include <bits/stdc++.h>
#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 long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF (ll)1'000'000'000'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 998244353
#define TC 1
/*
* 01/10/02/20 있는지 검사: 각 수에 대한 세그 만들기 (rmq) -> 온라인으로 가능
* * (ind, num)
* * seg[0][v]: arr[i][0]=v인 원소만 관리하는 세그
* 여기서 불가능 판정 -> 01/12 최소/최대인덱스 구해야함, 특정 구간에서 __이하 값이 등장하는 최소 인덱스 -> 위 세그에서 이분탐색
* 구간 2개로 확정하고 거기서 02/20 찾기: dnc
*/
void mergef(pii& p1, pii& p2, pii& res) {
	res.first = min(p1.first, p2.first);
	res.second = max(p1.second, p2.second);
}
pii merge(pii p1, pii p2) {
	pii res;
	res.first = min(p1.first, p2.first);
	res.second = max(p1.second, p2.second);
	return res;
}
struct segtree {
	int N;
	vector<int> inds, arr;
	vector<pii> tree;
	void init(int s, int e, int loc = 1) {
		if (s == e) {
			tree[loc] = pii(arr[s], arr[s]);
			return;
		}
		int m = s + e >> 1;
		init(s, m, loc * 2);
		init(m + 1, e, loc * 2 + 1);
		mergef(tree[loc * 2], tree[loc * 2 + 1], tree[loc]);
	}
	segtree(vector<int> iv, vector<int> v) :inds(iv), arr(v) {
		N = v.size();
		tree.resize(N * 4);
		init(0, N - 1);
	}
	segtree() {}
	pii _query(int s, int e, int l, int r, int loc = 1) {
		if (e < l || r < s) return pii(1e9, -1e9);
		if (l <= s && e <= r) return tree[loc];
		int m = s + e >> 1;
		return merge(_query(s, m, l, r, loc * 2), _query(m + 1, e, l, r, loc * 2 + 1));
	}
	pii query(int l, int r) {
		int ind1, ind2;
		ind1 = lower_bound(inds.begin(), inds.end(), l) - inds.begin();
		ind2 = upper_bound(inds.begin(), inds.end(), r) - inds.begin() - 1;
		if (ind1 <= ind2) return _query(0, N - 1, ind1, ind2);
		return pii(1e9, -1e9);
	}
	bool chk(int v, int dir, pii& p) {
		if (dir) return p.second >= v;
		else return p.first <= v;
	}
	int _findr(int s, int e, int l, int r, int v, int dir, int loc = 1) {
		if (e < l || r < s) return -1; //없다
		if (l <= s && e <= r) {
			if (!chk(v, dir, tree[loc])) return -1;
			if (s == e) return s;
			int m = s + e >> 1;
			if (chk(v, dir, tree[loc * 2])) return _findr(s, m, l, r, v, loc * 2);
			return _findr(m + 1, e, l, r, v, loc * 2 + 1);
		}
		int m = s + e >> 1;
		int res = _findr(s, m, l, r, v, dir, loc * 2);
		if (~res) return res;
		return _findr(m + 1, e, l, r, v, dir, loc * 2 + 1);
	}
	int _findl(int s, int e, int l, int r, int v, int dir, int loc = 1) {
		if (e < l || r < s) return -1; //없다
		if (l <= s && e <= r) {
			if (!chk(v, dir, tree[loc])) return -1;
			if (s == e) return s;
			int m = s + e >> 1;
			if (chk(v, dir, tree[loc * 2 + 1])) return _findl(m + 1, e, l, r, v, loc * 2 + 1);
			return _findl(s, m, l, r, v, loc * 2);
		}
		int m = s + e >> 1;
		int res = _findl(m + 1, e, l, r, v, dir, loc * 2 + 1);
		if (~res) return res;
		return _findl(s, m, l, r, v, dir, loc * 2);
	}
	int findr(int l, int r, int v, int dir) { //dir==1: v 이상인 원소 찾음 / dir==0: v 이하인 원소 찾음
		int ind = lower_bound(inds.begin(), inds.end(), l) - inds.begin();
		int ansv = _findr(0, N - 1, ind, N - 1, v, dir);
		if (!~ansv) return -1;
		int ans = inds[ansv];
		if (ans <= r) return ans;
		return -1;
	}
	int findl(int l, int r, int v, int dir) { //dir==1: v 이상인 원소 찾음 / dir==0: v 이하인 원소 찾음
		int ind = upper_bound(inds.begin(), inds.end(), r) - inds.begin() - 1;
		if (ind < 0) return -1;
		int ansv = _findl(0, N - 1, 0, ind, v, dir);
		if (!~ansv) return -1;
		int ans = inds[ansv];
		if (ans >= l) return ans;
		return -1;
	}
};
int arr[2][MAX];
vector<int> locs[2][MAX];
segtree pseg[2][MAX];
segtree allseg[2];
pii query[MAX];
int ans[MAX];

vector<int> segqv[2][MAX * 4];
vector<pii> qrange;
vector<int> qind;
int qcnt;

void upd(int s, int e, int l, int r, pii rg, int d, int i, int loc = 1) {
	if (e < l || r < s) return;
	if (l <= s && e <= r) {
		segqv[d][loc].push_back(qrange.size());
		qrange.push_back(rg);
		qind.push_back(i);
		return;
	}
	int m = s + e >> 1;
	upd(s, m, l, r, rg, d, i, loc * 2);
	upd(m + 1, e, l, r, rg, d, i, loc * 2 + 1);
}

void solve(int s, int e, int loc = 1) {
	int i;
	vector<int> qv;
	for (i = s; i <= e; i++) {
		segqv[0][loc].push_back(-i);
		segqv[1][loc].push_back(-i);
	}
	sort(segqv[0][loc].begin(), segqv[0][loc].end(), [&](int a, int b) {
		int l1, l2;
		if (a < 0) l1 = arr[0][-a];
		else l1 = qrange[a].first;
		if (b < 0) l2 = arr[0][-b];
		else l2 = qrange[b].first;
		if (l1 != l2) return l1 < l2;
		return a < b; // 업데이트(-) 먼저
		});
	sort(segqv[1][loc].begin(), segqv[1][loc].end(), [&](int a, int b) {
		int l1, l2;
		if (a < 0) l1 = arr[0][-a];
		else l1 = qrange[a].first;
		if (b < 0) l2 = arr[0][-b];
		else l2 = qrange[b].first;
		if (l1 != l2) return l1 > l2;
		return a < b; // 업데이트(-) 먼저
		});
	int mn, mx;
	mn = 1e9;
	mx = -1e9;
	for (auto q : segqv[0][loc]) {
		if (q < 0) mx = max(mx, arr[1][-q]);
		else if (mx >= qrange[q].second) ans[qind[q]] = 1;
	}
	for (auto q : segqv[1][loc]) {
		if (q < 0) mn = max(mn, arr[0][-q]);
		else if (mn <= qrange[q].second) ans[qind[q]] = 1;
	}
	if (s == e) return;
	int m = s + e >> 1;
	solve(s, m, loc * 2);
	solve(m + 1, e, loc * 2 + 1);
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M;
	cin >> N >> M;
	int i;
	for (i = 1; i <= N; i++) cin >> arr[0][i] >> arr[1][i];
	int X[2] = { 0, 0 };
	vector<int> vs[2];
	for (auto c : { 0, 1 }) {
		for (i = 1; i <= N; i++) vs[c].push_back(arr[c][i]);
		sort(vs[c].begin(), vs[c].end());
		vs[c].erase(unique(vs[c].begin(), vs[c].end()), vs[c].end());
		X[c] = vs[c].size();
		for (i = 1; i <= N; i++) {
			arr[c][i] = lower_bound(vs[c].begin(), vs[c].end(), arr[c][i]) - vs[c].begin() + 1;
			locs[c][arr[c][i]].push_back(i);
		}
		for (i = 1; i <= X[c]; i++) {
			vector<int> iv, v;
			for (auto ind : locs[c][i]) {
				iv.push_back(ind);
				v.push_back(arr[c ^ 1][ind]);
			}
			pseg[c][i] = segtree(iv, v);
		}
		vector<int> iv, v;
		for (i = 1; i <= N; i++) iv.push_back(i), v.push_back(arr[c][i]);
		allseg[c] = segtree(iv, v);
	}
	for (i = 1; i <= M; i++) {
		cin >> query[i].first >> query[i].second;
		int ind[2];
		ind[0] = lower_bound(vs[0].begin(), vs[0].end(), query[i].first) - vs[0].begin();
		ind[1] = lower_bound(vs[1].begin(), vs[1].end(), query[i].second) - vs[1].begin();
		if (ind[0] == vs[0].size()) continue;
		if (ind[1] == vs[1].size()) continue;
		if (vs[0][ind[0]] != query[i].first) continue;
		if (vs[1][ind[1]] != query[i].second) continue;
		ind[0]++;
		ind[1]++;
		int l, r;
		bool chk = true;
		if (arr[0][1] >= ind[0] && arr[1][1] >= ind[1]) l = 1;
		else if (arr[0][1] <= ind[0] && arr[1][1] <= ind[1]) l = 1;
		else {
			int cr = arr[0][1] < ind[0];
			int res1 = allseg[0].findr(1, N, ind[0], cr);
			int res2 = allseg[1].findr(1, N, ind[1], cr ^ 1);
			if (!~res1 && !~res2) chk = false;
			else if (!~res1) l = res2;
			else if (!~res2) l = res2;
			else l = min(res1, res2);
		}
		if (arr[0][N] >= ind[0] && arr[1][N] >= ind[1]) r = N;
		else if (arr[0][N] <= ind[0] && arr[1][N] <= ind[1]) r = N;
		else {
			int cr = arr[0][N] < ind[0];
			int res1 = allseg[0].findl(1, N, ind[0], cr);
			int res2 = allseg[1].findl(1, N, ind[1], cr ^ 1);
			if (!~res1 && !~res2) chk = false;
			else if (!~res1) r = res2;
			else if (!~res2) r = res2;
			else r = max(res1, res2);
		}
		if (!chk) continue;
		if (l > r) continue;
		int a, b;
		a = ind[0], b = ind[1];
		pii r0 = pseg[0][a].query(l, r);
		pii r1 = pseg[1][b].query(l, r);
		bool c01, c10, c21, c12;
		c10 = r0.first <= b;
		c12 = r0.second >= b;
		c01 = r1.first <= a;
		c21 = r1.second >= a;
		if (c10 && c01) {
			ans[i] = 1;
			continue;
		}
		if (c12 && c21) {
			ans[i] = 1;
			continue;
		}
		bool cc1, cc2;
		cc1 = c12 && c01;
		cc2 = c10 && c21;
		if (!cc1 && !cc2) continue;
		//cc1이 참일 경우 12/01 / 20을 찾아야함
		int dir0 = cc1;
		upd(1, N, l, r, pii(a, b), dir0, i);
		/*
		int a1, a2, b1, b2;
		a1 = pseg[0][a].findl(l, r, b, dir0);
		a2 = pseg[0][a].findr(l, r, b, dir0);
		b1 = pseg[1][b].findl(l, r, a, dir0 ^ 1);
		b2 = pseg[1][b].findr(l, r, a, dir0 ^ 1);
		for (auto qa : { a1, a2 }) for (auto qb : { b1, b2 }) {
			if (!~qa) continue;
			if (!~qb) continue;
			upd(1, N, min(qa, qb), max(qa, qb), pii(a, b), dir0, i);
		}
		*/
	}
	solve(1, N);
	for (i = 1; i <= M; i++) if (ans[i]) cout << i << bb;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 38
• Subtask 3: 0 / 22
• Subtask 4: 0 / 29