oj.uz

답안 #103148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103148 2019-03-29T06:44:43 Z E869120 새 집 (APIO18_new_home) C++14
0 / 100
 90 ms 25216 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <tuple>
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 << 17);

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);
}

set<int>Set[MAX_N];

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]); 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)); }
	for (int i = 1; i <= N; i++) VX.push_back(X[i]);
	for (int i = 1; i <= Q; i++) VX.push_back(L[i]);

	V1.init(VX.size() + 2);
	V2.init(VX.size() + 2);
	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());
	
	// 次に、本シミュレーション
	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:10:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
new_home.cpp: In function 'int main()':
new_home.cpp:191:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
new_home.cpp:206:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
new_home.cpp:177: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:178:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; i++) { scanf("%d%d%d%d", &X[i], &T[i], &A[i], &B[i]); vec.push_back(make_tuple(A[i], 1, i)); vec.push_back(make_tuple(B[i], 3, i)); X[i] *= 2; }
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:179:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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)); }
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12672 KB Output is correct
2 Correct 16 ms 12672 KB Output is correct
3 Correct 14 ms 12672 KB Output is correct
4 Runtime error 33 ms 25216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12672 KB Output is correct
2 Correct 16 ms 12672 KB Output is correct
3 Correct 14 ms 12672 KB Output is correct
4 Runtime error 33 ms 25216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 85 ms 20964 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 90 ms 20940 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12672 KB Output is correct
2 Correct 16 ms 12672 KB Output is correct
3 Correct 14 ms 12672 KB Output is correct
4 Runtime error 33 ms 25216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12672 KB Output is correct
2 Correct 16 ms 12672 KB Output is correct
3 Correct 14 ms 12672 KB Output is correct
4 Runtime error 33 ms 25216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -