Submission #103181

#	Time	Username	Problem	Language	Result	Execution time	Memory
103181		E869120	New Home (APIO18_new_home)	C++14	57 / 100	5072 ms	456588 KiB

new_home

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <tuple>
#include <cassert>
using namespace std;
#pragma warning (disable: 4996)

// ------------------------------------------------------- 特殊な場合を除く -------------------------------------

class SegmentTree {
public:
	vector<priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>>>dat;
	vector<bool> used; vector<int> cl, cr;
	int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2);
	}
	void add_(int l, int r, int a, int b, int x, int u) {
		if (l <= a && b <= r) { dat[u].push(make_pair(x, used.size())); return; }
		if (r <= a || b <= l) return;

		add_(l, r, a, (a + b) >> 1, x, u * 2);
		add_(l, r, (a + b) >> 1, b, x, u * 2 + 1);
	}
	int add(int l, int r, int x) {
		add_(l, r, 0, size_, x, 1);
		used.push_back(false); cl.push_back(l); cr.push_back(r);
		return used.size() - 1;
	}
	void query(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) {
			while (!dat[u].empty()) {
				int t = dat[u].top().second;
				if (used[t] == true) dat[u].pop();
				else break;
			}
			return;
		}
		if (r <= a || b <= l) return;

		query(l, r, a, (a + b) >> 1, u * 2);
		query(l, r, (a + b) >> 1, b, u * 2 + 1);
	}
	void dels(int num) {
		used[num] = true;
		query(cl[num], cr[num], 0, size_, 1);
	}

	int answer(int pos) {
		pos += size_; int ans = -(1 << 30);

		while (pos >= 1) {
			if (!dat[pos].empty()) ans = max(ans, dat[pos].top().first);
			pos >>= 1;
		}
		return ans;
	}
};

const int MAX_N = (1 << 19);

int N, K, Q, R, X[MAX_N], T[MAX_N], A[MAX_N], B[MAX_N], L[MAX_N], Y[MAX_N], Answer[MAX_N], cnt1[MAX_N], cnt;
set<pair<int, int>> dishes[MAX_N]; map<tuple<int, int, int>, int>Map;

SegmentTree V1, V2; vector<int>VX; vector<tuple<int, int, int>>vec;

void delete_vision(int cl, int cr) {
	if (R == 1) return;
	if (cr != -2) V1.dels(Map[make_tuple(cl, cr, 1)]);
	if (cl != -1) V2.dels(Map[make_tuple(cl, cr, 2)]);
}

void add_vision(int cl, int cr) {
	if (R == 1) {
		if (cl != -1 && cr != -2) VX.push_back((X[cl] + X[cr]) / 2);
		return;
	}
	if (cl != -1 && cr != -2) {
		int pos1 = lower_bound(VX.begin(), VX.end(), X[cl]) - VX.begin();
		int pos2 = lower_bound(VX.begin(), VX.end(), (X[cl] + X[cr]) / 2) - VX.begin();
		int pos3 = lower_bound(VX.begin(), VX.end(), X[cr]) - VX.begin();

		int Z1 = V1.add(pos2, pos3 + 1, X[cr]); Map[make_tuple(cl, cr, 1)] = Z1;
		int Z2 = V2.add(pos1, pos2 + 1, -X[cl]); Map[make_tuple(cl, cr, 2)] = Z2;
	}
	else if (cr != -2) {
		int pos1 = lower_bound(VX.begin(), VX.end(), X[cr]) - VX.begin();

		int Z1 = V1.add(0, pos1 + 1, X[cr]); Map[make_tuple(cl, cr, 1)] = Z1;
	}
	else if (cl != -1) {
		int pos1 = lower_bound(VX.begin(), VX.end(), X[cl]) - VX.begin();

		int Z2 = V2.add(pos1, VX.size() + 1, -X[cl]); Map[make_tuple(cl, cr, 2)] = Z2;
	}
}

void delete_relation(int ty, int pos) {
	if (ty == 1) {
		// 2 点の場合
		auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
		auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));

		int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
		int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }

		delete_vision(P1, P2);
	}
	if (ty == 2) {
		auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
		auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos + 1));

		int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
		int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }

		delete_vision(P1, pos);
		delete_vision(pos, P2);
	}
}

void add_relation(int ty, int pos) {
	if (ty == 1) {
		// 3 点の場合
		auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
		auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos + 1));

		int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
		int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }

		add_vision(P1, pos);
		add_vision(pos, P2);
	}
	if (ty == 2) {
		// 2 点の場合
		auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
		auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));

		int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
		int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }

		add_vision(P1, P2);
	}
}

void add(int pos) {
	cnt1[T[pos]]++; if (cnt1[T[pos]] == 1) cnt++;
	delete_relation(1, pos);
	dishes[T[pos]].insert(make_pair(X[pos], pos));
	add_relation(1, pos);
}

void lose(int pos) {
	cnt1[T[pos]]--; if (cnt1[T[pos]] == 0) cnt--;

	delete_relation(2, pos);
	dishes[T[pos]].erase(make_pair(X[pos], pos));
	add_relation(2, pos);
}

int getval(int pos) {
	int pos1 = lower_bound(VX.begin(), VX.end(), pos) - VX.begin();
	int val1 = V1.answer(pos1) - pos;

	int pos2 = lower_bound(VX.begin(), VX.end(), pos) - VX.begin();
	int val2 = V2.answer(pos2) + pos;

	return max(val1, val2);
}

// ---------------------------------- 特殊な場合に対処 -----------------------------------

int RR = 2; vector<int>G[MAX_N]; bool uses[MAX_N * 2];

void solve_partial() {
	for (int i = 1; i <= N; i++) G[T[i]].push_back(X[i]);
	for (int i = 1; i <= K; i++) sort(G[i].begin(), G[i].end());

	vector<tuple<int, int, int, int>> Z;
	for (int i = 1; i <= Q; i++) Z.push_back(make_tuple(L[i], 3, i, 0));

	int cntv = 0;
	for (int i = 1; i <= K; i++) {
		if (G[i].size() == 0) {
			for (int j = 1; j <= Q; j++) Answer[j] = -1;
			return;
		}

		Z.push_back(make_tuple(0, 1, G[i][0], cntv));
		Z.push_back(make_tuple(G[i][0], 4, G[i][0], cntv));
		cntv++;

		for (int j = 0; j < G[i].size() - 1; j++) {
			int cl = G[i][j], cr = G[i][j + 1];
			Z.push_back(make_tuple(cl, 2, -cl, cntv));
			Z.push_back(make_tuple((cl + cr) >> 1, 5, -cl, cntv)); cntv++;
			Z.push_back(make_tuple((cl + cr) >> 1, 1, cr, cntv));
			Z.push_back(make_tuple(cr, 4, cr, cntv)); cntv++;
		}

		Z.push_back(make_tuple(G[i][G[i].size() - 1], 2, -G[i][G[i].size() - 1], cntv)); cntv++;
	}

	sort(Z.begin(), Z.end());

	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> que1, que2;

	for (int i = 0; i < Z.size(); i++) {
		if (get<1>(Z[i]) == 1) {
			que1.push(make_pair(get<2>(Z[i]), get<3>(Z[i])));
		}
		if (get<1>(Z[i]) == 2) {
			que2.push(make_pair(get<2>(Z[i]), get<3>(Z[i])));
		}
		if (get<1>(Z[i]) == 3) {
			int val1 = 0; if (!que1.empty()) val1 = que1.top().first - get<0>(Z[i]);
			int val2 = 0; if (!que2.empty()) val2 = que2.top().first + get<0>(Z[i]);
			Answer[get<2>(Z[i])] = max(val1, val2);
		}
		if (get<1>(Z[i]) == 4) {
			uses[get<3>(Z[i])] = true;
			while (!que1.empty()) { if (uses[que1.top().second] == true) que1.pop(); else break; }
		}
		if (get<1>(Z[i]) == 5) {
			uses[get<3>(Z[i])] = true;
			while (!que2.empty()) { if (uses[que2.top().second] == true) que2.pop(); else break; }
		}
	}
	return;
}

int main() {
	scanf("%d%d%d", &N, &K, &Q);
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d%d", &X[i], &T[i], &A[i], &B[i]); if (!(A[i] == 1 && B[i] == 100000000)) RR = 1;
		vec.push_back(make_tuple(A[i], 1, i)); vec.push_back(make_tuple(B[i], 3, i)); X[i] *= 2;
	}
	for (int i = 1; i <= Q; i++) {
		scanf("%d%d", &L[i], &Y[i]);
		L[i] *= 2;
		vec.push_back(make_tuple(Y[i], 2, i));
	}

	if (RR == 2) {
		solve_partial();
	}
	if (RR == 1) {
		for (int i = 1; i <= N; i++) VX.push_back(X[i]);
		for (int i = 1; i <= Q; i++) VX.push_back(L[i]);

		sort(vec.begin(), vec.end());
		sort(VX.begin(), VX.end());

		// まず 1 回シミュレーションを行う
		R = 1;

		for (int i = 0; i < vec.size(); i++) {
			if (get<1>(vec[i]) == 1) {
				add(get<2>(vec[i]));
			}
			if (get<1>(vec[i]) == 3) {
				lose(get<2>(vec[i]));
			}
		}

		sort(VX.begin(), VX.end());
		VX.erase(unique(VX.begin(), VX.end()), VX.end());
		V1.init(VX.size() + 2);
		V2.init(VX.size() + 2);

		// 次に、本シミュレーション
		R = 2;

		for (int i = 0; i < vec.size(); i++) {
			if (get<1>(vec[i]) == 1) {
				add(get<2>(vec[i]));
			}
			if (get<1>(vec[i]) == 2) {
				Answer[get<2>(vec[i])] = getval(L[get<2>(vec[i])]);
				if (cnt != K) Answer[get<2>(vec[i])] = -2;
			}
			if (get<1>(vec[i]) == 3) {
				lose(get<2>(vec[i]));
			}
		}
	}

	for (int i = 1; i <= Q; i++) printf("%d\n", Answer[i] / 2);
	return 0;
}

Compilation message (stderr)

new_home.cpp:11:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
new_home.cpp: In function 'void solve_partial()':
new_home.cpp:199:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < G[i].size() - 1; j++) {
                   ~~^~~~~~~~~~~~~~~~~
new_home.cpp:214:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z.size(); i++) {
                  ~~^~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:263:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < vec.size(); i++) {
                   ~~^~~~~~~~~~~~
new_home.cpp:280:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < vec.size(); i++) {
                   ~~^~~~~~~~~~~~
new_home.cpp:239:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &K, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:241:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &X[i], &T[i], &A[i], &B[i]); if (!(A[i] == 1 && B[i] == 100000000)) RR = 1;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:245:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &L[i], &Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20