oj.uz

답안 #103167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103167 2019-03-29T07:11:03 Z E869120 새 집 (APIO18_new_home) C++14
0 / 100
 1896 ms 659656 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;
	}
};

class SegmentTree2 {
public:
	vector<int>dat;
	int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, -(1 << 30));
	}
	void add_(int l, int r, int a, int b, int x, int u) {
		if (l <= a && b <= r) { dat[u] = max(dat[u], u); 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);
		return -1;
	}

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

		while (pos >= 1) {
			ans = max(ans, dat[pos]);
			pos >>= 1;
		}
		return ans;
	}
};

const int MAX_N = (1 << 19);

int N, K, Q, R, RR, 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;
SegmentTree2 V3, V4;

void delete_vision(int cl, int cr) {
	if (R == 1 || RR == 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();

		if (RR == 1) {
			V3.add(pos2, pos3 + 1, X[cr]);
			V4.add(pos1, pos2 + 1, -X[cl]);
		}
		if (RR == 2) {
			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();
		
		if (RR == 1) {
			V3.add(0, pos1 + 1, X[cr]);
		}
		if (RR == 2) {
			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();

		if (RR == 1) {
			V4.add(pos1, VX.size() + 1, -X[cl]);
		}
		if (RR == 2) {
			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) {
	if (RR == 1) {
		int pos1 = lower_bound(VX.begin(), VX.end(), pos) - VX.begin();
		int val1 = V3.answer(pos1) - pos;

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

		return max(val1, val2);
	}
	if (RR == 2) {
		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 main() {
	scanf("%d%d%d", &N, &K, &Q); RR = 1;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d%d%d", &X[i], &T[i], &A[i], &B[i]); A[i] = 100000001 - A[i]; B[i] = 100000001 - B[i]; swap(A[i], B[i]); if (B[i] != 100000000) RR = 2;
		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]); Y[i] = 100000001 - 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]);

	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:10:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
new_home.cpp: In function 'int main()':
new_home.cpp:254:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
new_home.cpp:271:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
new_home.cpp: In function 'int getval(int)':
new_home.cpp:232:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
new_home.cpp: In function 'int main()':
new_home.cpp:235: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); RR = 1;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:237: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]); A[i] = 100000001 - A[i]; B[i] = 100000001 - B[i]; swap(A[i], B[i]); if (B[i] != 100000000) RR = 2;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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", &L[i], &Y[i]); Y[i] = 100000001 - Y[i];
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 49784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 49784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1148 ms 391248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1896 ms 659656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 49784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 49784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -