oj.uz

Submission #103171

# Submission time Handle Problem Language Result Execution time Memory
103171 2019-03-29T07:16:18 Z E869120 New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 162632 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], x); 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());

	if (RR == 1) {
		V3.init(VX.size() + 2);
		V4.init(VX.size() + 2);
	}
	if (RR == 2) {
		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:278: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25080 KB Output is correct
2 Correct 28 ms 24960 KB Output is correct
3 Correct 27 ms 24952 KB Output is correct
4 Correct 27 ms 25080 KB Output is correct
5 Correct 31 ms 25212 KB Output is correct
6 Correct 35 ms 25592 KB Output is correct
7 Correct 28 ms 25344 KB Output is correct
8 Correct 35 ms 25564 KB Output is correct
9 Correct 29 ms 25344 KB Output is correct
10 Correct 35 ms 25720 KB Output is correct
11 Correct 30 ms 25564 KB Output is correct
12 Correct 30 ms 25592 KB Output is correct
13 Correct 29 ms 25336 KB Output is correct
14 Correct 28 ms 25472 KB Output is correct
15 Correct 32 ms 25600 KB Output is correct
16 Correct 33 ms 25556 KB Output is correct
17 Correct 31 ms 25596 KB Output is correct
18 Correct 32 ms 25592 KB Output is correct
19 Correct 30 ms 25600 KB Output is correct
20 Correct 34 ms 25592 KB Output is correct
21 Correct 33 ms 25080 KB Output is correct
22 Correct 32 ms 25344 KB Output is correct
23 Correct 29 ms 25472 KB Output is correct
24 Correct 29 ms 25592 KB Output is correct
25 Correct 37 ms 25592 KB Output is correct
26 Correct 35 ms 25592 KB Output is correct
27 Correct 29 ms 25208 KB Output is correct
28 Correct 32 ms 25592 KB Output is correct
29 Correct 31 ms 25592 KB Output is correct
30 Correct 27 ms 25344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25080 KB Output is correct
2 Correct 28 ms 24960 KB Output is correct
3 Correct 27 ms 24952 KB Output is correct
4 Correct 27 ms 25080 KB Output is correct
5 Correct 31 ms 25212 KB Output is correct
6 Correct 35 ms 25592 KB Output is correct
7 Correct 28 ms 25344 KB Output is correct
8 Correct 35 ms 25564 KB Output is correct
9 Correct 29 ms 25344 KB Output is correct
10 Correct 35 ms 25720 KB Output is correct
11 Correct 30 ms 25564 KB Output is correct
12 Correct 30 ms 25592 KB Output is correct
13 Correct 29 ms 25336 KB Output is correct
14 Correct 28 ms 25472 KB Output is correct
15 Correct 32 ms 25600 KB Output is correct
16 Correct 33 ms 25556 KB Output is correct
17 Correct 31 ms 25596 KB Output is correct
18 Correct 32 ms 25592 KB Output is correct
19 Correct 30 ms 25600 KB Output is correct
20 Correct 34 ms 25592 KB Output is correct
21 Correct 33 ms 25080 KB Output is correct
22 Correct 32 ms 25344 KB Output is correct
23 Correct 29 ms 25472 KB Output is correct
24 Correct 29 ms 25592 KB Output is correct
25 Correct 37 ms 25592 KB Output is correct
26 Correct 35 ms 25592 KB Output is correct
27 Correct 29 ms 25208 KB Output is correct
28 Correct 32 ms 25592 KB Output is correct
29 Correct 31 ms 25592 KB Output is correct
30 Correct 27 ms 25344 KB Output is correct
31 Correct 3482 ms 162632 KB Output is correct
32 Correct 801 ms 59988 KB Output is correct
33 Correct 2749 ms 144420 KB Output is correct
34 Correct 3600 ms 159088 KB Output is correct
35 Correct 3420 ms 157064 KB Output is correct
36 Correct 2685 ms 145760 KB Output is correct
37 Correct 2130 ms 145916 KB Output is correct
38 Correct 1817 ms 142180 KB Output is correct
39 Correct 1203 ms 141700 KB Output is correct
40 Correct 1324 ms 141280 KB Output is correct
41 Correct 1925 ms 101140 KB Output is correct
42 Correct 2128 ms 104292 KB Output is correct
43 Correct 175 ms 34156 KB Output is correct
44 Correct 1909 ms 102752 KB Output is correct
45 Correct 1575 ms 97380 KB Output is correct
46 Correct 1311 ms 96140 KB Output is correct
47 Correct 652 ms 92644 KB Output is correct
48 Correct 686 ms 92896 KB Output is correct
49 Correct 896 ms 96456 KB Output is correct
50 Correct 1064 ms 102292 KB Output is correct
51 Correct 970 ms 95452 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3398 ms 81372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 98064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25080 KB Output is correct
2 Correct 28 ms 24960 KB Output is correct
3 Correct 27 ms 24952 KB Output is correct
4 Correct 27 ms 25080 KB Output is correct
5 Correct 31 ms 25212 KB Output is correct
6 Correct 35 ms 25592 KB Output is correct
7 Correct 28 ms 25344 KB Output is correct
8 Correct 35 ms 25564 KB Output is correct
9 Correct 29 ms 25344 KB Output is correct
10 Correct 35 ms 25720 KB Output is correct
11 Correct 30 ms 25564 KB Output is correct
12 Correct 30 ms 25592 KB Output is correct
13 Correct 29 ms 25336 KB Output is correct
14 Correct 28 ms 25472 KB Output is correct
15 Correct 32 ms 25600 KB Output is correct
16 Correct 33 ms 25556 KB Output is correct
17 Correct 31 ms 25596 KB Output is correct
18 Correct 32 ms 25592 KB Output is correct
19 Correct 30 ms 25600 KB Output is correct
20 Correct 34 ms 25592 KB Output is correct
21 Correct 33 ms 25080 KB Output is correct
22 Correct 32 ms 25344 KB Output is correct
23 Correct 29 ms 25472 KB Output is correct
24 Correct 29 ms 25592 KB Output is correct
25 Correct 37 ms 25592 KB Output is correct
26 Correct 35 ms 25592 KB Output is correct
27 Correct 29 ms 25208 KB Output is correct
28 Correct 32 ms 25592 KB Output is correct
29 Correct 31 ms 25592 KB Output is correct
30 Correct 27 ms 25344 KB Output is correct
31 Correct 3482 ms 162632 KB Output is correct
32 Correct 801 ms 59988 KB Output is correct
33 Correct 2749 ms 144420 KB Output is correct
34 Correct 3600 ms 159088 KB Output is correct
35 Correct 3420 ms 157064 KB Output is correct
36 Correct 2685 ms 145760 KB Output is correct
37 Correct 2130 ms 145916 KB Output is correct
38 Correct 1817 ms 142180 KB Output is correct
39 Correct 1203 ms 141700 KB Output is correct
40 Correct 1324 ms 141280 KB Output is correct
41 Correct 1925 ms 101140 KB Output is correct
42 Correct 2128 ms 104292 KB Output is correct
43 Correct 175 ms 34156 KB Output is correct
44 Correct 1909 ms 102752 KB Output is correct
45 Correct 1575 ms 97380 KB Output is correct
46 Correct 1311 ms 96140 KB Output is correct
47 Correct 652 ms 92644 KB Output is correct
48 Correct 686 ms 92896 KB Output is correct
49 Correct 896 ms 96456 KB Output is correct
50 Correct 1064 ms 102292 KB Output is correct
51 Correct 970 ms 95452 KB Output is correct
52 Correct 1222 ms 73840 KB Output is correct
53 Correct 1185 ms 70532 KB Output is correct
54 Correct 2421 ms 114692 KB Output is correct
55 Correct 1612 ms 102000 KB Output is correct
56 Correct 1520 ms 100716 KB Output is correct
57 Correct 2031 ms 105688 KB Output is correct
58 Correct 2009 ms 102680 KB Output is correct
59 Correct 1731 ms 100704 KB Output is correct
60 Correct 2069 ms 106608 KB Output is correct
61 Correct 101 ms 34016 KB Output is correct
62 Correct 1268 ms 76100 KB Output is correct
63 Correct 1747 ms 105064 KB Output is correct
64 Correct 1828 ms 110560 KB Output is correct
65 Correct 2268 ms 112736 KB Output is correct
66 Correct 2287 ms 105836 KB Output is correct
67 Correct 824 ms 57720 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 25080 KB Output is correct
2 Correct 28 ms 24960 KB Output is correct
3 Correct 27 ms 24952 KB Output is correct
4 Correct 27 ms 25080 KB Output is correct
5 Correct 31 ms 25212 KB Output is correct
6 Correct 35 ms 25592 KB Output is correct
7 Correct 28 ms 25344 KB Output is correct
8 Correct 35 ms 25564 KB Output is correct
9 Correct 29 ms 25344 KB Output is correct
10 Correct 35 ms 25720 KB Output is correct
11 Correct 30 ms 25564 KB Output is correct
12 Correct 30 ms 25592 KB Output is correct
13 Correct 29 ms 25336 KB Output is correct
14 Correct 28 ms 25472 KB Output is correct
15 Correct 32 ms 25600 KB Output is correct
16 Correct 33 ms 25556 KB Output is correct
17 Correct 31 ms 25596 KB Output is correct
18 Correct 32 ms 25592 KB Output is correct
19 Correct 30 ms 25600 KB Output is correct
20 Correct 34 ms 25592 KB Output is correct
21 Correct 33 ms 25080 KB Output is correct
22 Correct 32 ms 25344 KB Output is correct
23 Correct 29 ms 25472 KB Output is correct
24 Correct 29 ms 25592 KB Output is correct
25 Correct 37 ms 25592 KB Output is correct
26 Correct 35 ms 25592 KB Output is correct
27 Correct 29 ms 25208 KB Output is correct
28 Correct 32 ms 25592 KB Output is correct
29 Correct 31 ms 25592 KB Output is correct
30 Correct 27 ms 25344 KB Output is correct
31 Correct 3482 ms 162632 KB Output is correct
32 Correct 801 ms 59988 KB Output is correct
33 Correct 2749 ms 144420 KB Output is correct
34 Correct 3600 ms 159088 KB Output is correct
35 Correct 3420 ms 157064 KB Output is correct
36 Correct 2685 ms 145760 KB Output is correct
37 Correct 2130 ms 145916 KB Output is correct
38 Correct 1817 ms 142180 KB Output is correct
39 Correct 1203 ms 141700 KB Output is correct
40 Correct 1324 ms 141280 KB Output is correct
41 Correct 1925 ms 101140 KB Output is correct
42 Correct 2128 ms 104292 KB Output is correct
43 Correct 175 ms 34156 KB Output is correct
44 Correct 1909 ms 102752 KB Output is correct
45 Correct 1575 ms 97380 KB Output is correct
46 Correct 1311 ms 96140 KB Output is correct
47 Correct 652 ms 92644 KB Output is correct
48 Correct 686 ms 92896 KB Output is correct
49 Correct 896 ms 96456 KB Output is correct
50 Correct 1064 ms 102292 KB Output is correct
51 Correct 970 ms 95452 KB Output is correct
52 Incorrect 3398 ms 81372 KB Output isn't correct
53 Halted 0 ms 0 KB -