oj.uz

Submission #103180

# Submission time Handle Problem Language Result Execution time Memory
103180 2019-03-29T07:42:07 Z E869120 New Home (APIO18_new_home) C++14
10 / 100
 786 ms 119548 KB 
#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));
	}

	assert(RR == 2);

	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

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:265:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < vec.size(); i++) {
                   ~~^~~~~~~~~~~~
new_home.cpp:282: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 74488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 74488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 98828 KB Output is correct
2 Correct 623 ms 109876 KB Output is correct
3 Correct 786 ms 119216 KB Output is correct
4 Correct 765 ms 113080 KB Output is correct
5 Correct 567 ms 109616 KB Output is correct
6 Correct 590 ms 109876 KB Output is correct
7 Correct 619 ms 119548 KB Output is correct
8 Correct 623 ms 112944 KB Output is correct
9 Correct 705 ms 111756 KB Output is correct
10 Correct 696 ms 111044 KB Output is correct
11 Correct 667 ms 109616 KB Output is correct
12 Correct 574 ms 110632 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 109920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 74488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 74488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -