oj.uz

Submission #112045

# Submission time Handle Problem Language Result Execution time Memory
112045 2019-05-17T07:25:40 Z ecasdqina New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 50956 KB 
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

struct LazySegmentTree {
	std::vector<int> seg, lazy;
	int sz = 1;
	
	LazySegmentTree(int n) {
		while(sz < n) sz <<= 1;
		seg.assign(sz * 2 - 1, 0);
		lazy.assign(sz * 2 - 1, 0);
	}
	void update(int k, int x) {
		get(k, k + 1);
		k += sz - 1;
		seg[k] = x;
		
		while(k) {
			k = (k - 1) >> 1;
			seg[k] = std::max(seg[2 * k + 1], seg[2 * k + 2]);
		}
	}
	void push(int k) {
		if(k < sz) {
			lazy[2 * k + 1] += lazy[k];
			lazy[2 * k + 2] += lazy[k];
		}
		seg[k] += lazy[k];
		lazy[k] = 0;
	}
	int get(int a, int b, int k, int l, int r) {
		push(k);
		if(b <= l || r <= a) return 0;
		if(a <= l && r <= b) return seg[k];
		int L = get(a, b, 2 * k + 1, l, (l + r) >> 1);
		int R = get(a, b, 2 * k + 2, (l + r) >> 1, r);
		return std::max(L, R);
	}
	int get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
	void add(int a, int b, int k, int l, int r, int x) {
		push(k);
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			lazy[k] += x;
			push(k);
			return;
		}
		add(a, b, 2 * k + 1, l, (l + r) >> 1, x);
		add(a, b, 2 * k + 2, (l + r) >> 1, r, x);
		seg[k] = std::max(seg[2 * k + 1], seg[2 * k + 2]);
	}
	void add(int a, int b, int x) {
		add(a, b, 0, 0, sz, x);
	};
	int operator[](int k) {
		return get(k, k + 1);
	}
};

int main() {
	int n, q, K; scanf("%d%d%d", &n, &K, &q);
	std::vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
	for(int i = 0; i < n; i++) {
		scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]); t[i]--;
	}
	for(int i = 0; i < q; i++) scanf("%d%d", &l[i], &y[i]);
	
	std::function<int (std::set<std::pair<int, int>>&, int)> calcDist = [](std::set<std::pair<int, int>>& st, int t) {
		auto it = st.lower_bound(std::make_pair(t, -1));
		if(it == st.end()) it = std::prev(it);
		if(it == st.begin()) return std::abs((*it).first - t);
		return std::min(std::abs((*it).first - t),
						 std::abs((*std::prev(it)).first - t));
	};
	
	std::vector<int> ans(q, -1);
	if(n <= 400 and q <= 400) {
		for(int i = 0; i < q; i++) {
			std::vector<int> vec(K, 1 << 30);
			for(int j = 0; j < n; j++) {
				if(!(a[j] <= y[i] and y[i] <= b[j])) continue;
				vec[t[j]] = std::min(vec[t[j]], std::abs(x[j] - l[i]));
			}
			
			
			for(int j = 0; j < K; j++) {
				if(vec[j] == 1 << 30) {
					ans[i] = -1;
					break;
				}
				ans[i] = std::max(ans[i], vec[j]);
			}
		}
	} else if(K <= 400) {
		std::vector<std::pair<int, int>> A, B;
		for(int i = 0; i < n; i++) {
			A.push_back({a[i], i});
			B.push_back({b[i] + 1, i});
		}
		sort(begin(A), end(A)); sort(begin(B), end(B));
		
		std::vector<std::pair<int, int>> query;
		for(int i = 0; i < q; i++) query.push_back({y[i], i});
		sort(begin(query), end(query));
		
		int curA = 0, curB = 0;
		std::vector<std::set<std::pair<int, int>>> vec(K);
		for(auto YYS: query) {
			int L = l[YYS.second], Y = y[YYS.second];
			while(curA < A.size() and A[curA].first <= Y) {
				int p = A[curA++].second;
				vec[t[p]].insert({x[p], p});
			}
			while(curB < B.size() and B[curB].first <= Y) {
				int p = B[curB++].second;
				vec[t[p]].erase({x[p], p});
			}
			
			int ret = 0;
			for(int k = 0; k < K; k++) {
				if(vec[k].empty()) {
					ret = -1;
					break;
				}
				
				ret = std::max(ret, calcDist(vec[k], L));
			}
			ans[YYS.second] = ret;
		}
	} else {
		for(int i = 0; i < n; i++) assert(a[i] == 1 and b[i] == 1e8);
		
		std::vector<std::pair<int, std::pair<int, int>>> A;
		std::vector<std::vector<int>> vec(K);
		for(int i = 0; i < n; i++) {
			vec[t[i]].push_back(x[i]);
			A.push_back({x[i], {t[i], 1}});
		}
		for(int k = 0; k < K; k++) {
			if(vec[k].empty()) {
				while(K--) printf("-1\n");
				return 0;
			}
			sort(begin(vec[k]), end(vec[k]));
			A.push_back({(vec[k][0] + 1) >> 1, {k, 0}});
			for(int i = 0; i < vec[k].size() - 1; i++) {
				A.push_back({(vec[k][i] + vec[k][i + 1] + 1) >> 1, {k, 0}});
			}
		}
		sort(begin(A), end(A));
		
		std::vector<std::pair<int, int>> query(1, {0, 0});
		for(int i = 0; i < q; i++) query.push_back({l[i], i});
		sort(begin(query), end(query));
		
		int cur = 0;
		LazySegmentTree X(K), Y(K);
		for(int i = 0; i < K; i++) Y.update(i, vec[i].front());
		for(int i = 0; i < query.size(); i++) {
			int L = query[i].first;
			if(i) {
				X.add(0, K, query[i].first - query[i - 1].first);
				Y.add(0, K, query[i - 1].first - query[i].first);
			}
			while(cur < A.size() and A[cur].first <= L) {
				int type = A[cur].second.second, p = A[cur].second.first, x = A[cur++].first;
				
				if(type == 1) {
					X.update(p, L - x);
					Y.update(p, 0);
					vec[p].erase(begin(vec[p]));
				} else if(type == 0) {
					Y.update(p, vec[p].front() - L);
					X.update(p, 0);
				}
			}
			
			/*
			cout << "X: "; for(int j = 0; j < K; j++) cout << X[j] << " "; cout << endl;
			cout << "Y: "; for(int j = 0; j < K; j++) cout << Y[j] << " "; cout << endl;
			cout << endl;
			*/
			
			if(i) ans[query[i].second] = std::max(X.seg[0], Y.seg[0]);
		}
	}
	for(auto v: ans) printf("%d\n", v);
	return 0;
}
/*
4 2 4
3 1 1 100000000
9 2 1 100000000
7 2 1 100000000
4 1 1 100000000
5 3
5 6
5 9
1 10
*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curA < A.size() and A[curA].first <= Y) {
          ~~~~~^~~~~~~~~~
new_home.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curB < B.size() and B[curB].first <= Y) {
          ~~~~~^~~~~~~~~~
new_home.cpp:160:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < vec[k].size() - 1; i++) {
                   ~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < query.size(); i++) {
                  ~~^~~~~~~~~~~~~~
new_home.cpp:179:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(cur < A.size() and A[cur].first <= L) {
          ~~~~^~~~~~~~~~
new_home.cpp:75:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q, K; scanf("%d%d%d", &n, &K, &q);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:78: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]); t[i]--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:80:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < q; i++) scanf("%d%d", &l[i], &y[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 3261 ms 6432 KB Output is correct
32 Correct 94 ms 4916 KB Output is correct
33 Correct 250 ms 4408 KB Output is correct
34 Correct 2037 ms 4456 KB Output is correct
35 Correct 1241 ms 6380 KB Output is correct
36 Correct 251 ms 6196 KB Output is correct
37 Correct 170 ms 3820 KB Output is correct
38 Correct 103 ms 3696 KB Output is correct
39 Correct 86 ms 3728 KB Output is correct
40 Correct 85 ms 3692 KB Output is correct
41 Correct 345 ms 3692 KB Output is correct
42 Correct 262 ms 3692 KB Output is correct
43 Correct 420 ms 6380 KB Output is correct
44 Correct 283 ms 3664 KB Output is correct
45 Correct 138 ms 3696 KB Output is correct
46 Correct 77 ms 3692 KB Output is correct
47 Correct 70 ms 3728 KB Output is correct
48 Correct 69 ms 3564 KB Output is correct
49 Correct 94 ms 3564 KB Output is correct
50 Correct 234 ms 3692 KB Output is correct
51 Correct 142 ms 3692 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 26392 KB Output is correct
2 Correct 3162 ms 29784 KB Output is correct
3 Correct 1699 ms 50828 KB Output is correct
4 Correct 1242 ms 27892 KB Output is correct
5 Correct 1046 ms 29768 KB Output is correct
6 Correct 2132 ms 29768 KB Output is correct
7 Correct 1466 ms 50956 KB Output is correct
8 Correct 1255 ms 27800 KB Output is correct
9 Correct 1156 ms 24836 KB Output is correct
10 Execution timed out 5019 ms 29640 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 16892 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 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 3261 ms 6432 KB Output is correct
32 Correct 94 ms 4916 KB Output is correct
33 Correct 250 ms 4408 KB Output is correct
34 Correct 2037 ms 4456 KB Output is correct
35 Correct 1241 ms 6380 KB Output is correct
36 Correct 251 ms 6196 KB Output is correct
37 Correct 170 ms 3820 KB Output is correct
38 Correct 103 ms 3696 KB Output is correct
39 Correct 86 ms 3728 KB Output is correct
40 Correct 85 ms 3692 KB Output is correct
41 Correct 345 ms 3692 KB Output is correct
42 Correct 262 ms 3692 KB Output is correct
43 Correct 420 ms 6380 KB Output is correct
44 Correct 283 ms 3664 KB Output is correct
45 Correct 138 ms 3696 KB Output is correct
46 Correct 77 ms 3692 KB Output is correct
47 Correct 70 ms 3728 KB Output is correct
48 Correct 69 ms 3564 KB Output is correct
49 Correct 94 ms 3564 KB Output is correct
50 Correct 234 ms 3692 KB Output is correct
51 Correct 142 ms 3692 KB Output is correct
52 Runtime error 49 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 3261 ms 6432 KB Output is correct
32 Correct 94 ms 4916 KB Output is correct
33 Correct 250 ms 4408 KB Output is correct
34 Correct 2037 ms 4456 KB Output is correct
35 Correct 1241 ms 6380 KB Output is correct
36 Correct 251 ms 6196 KB Output is correct
37 Correct 170 ms 3820 KB Output is correct
38 Correct 103 ms 3696 KB Output is correct
39 Correct 86 ms 3728 KB Output is correct
40 Correct 85 ms 3692 KB Output is correct
41 Correct 345 ms 3692 KB Output is correct
42 Correct 262 ms 3692 KB Output is correct
43 Correct 420 ms 6380 KB Output is correct
44 Correct 283 ms 3664 KB Output is correct
45 Correct 138 ms 3696 KB Output is correct
46 Correct 77 ms 3692 KB Output is correct
47 Correct 70 ms 3728 KB Output is correct
48 Correct 69 ms 3564 KB Output is correct
49 Correct 94 ms 3564 KB Output is correct
50 Correct 234 ms 3692 KB Output is correct
51 Correct 142 ms 3692 KB Output is correct
52 Correct 1278 ms 26392 KB Output is correct
53 Correct 3162 ms 29784 KB Output is correct
54 Correct 1699 ms 50828 KB Output is correct
55 Correct 1242 ms 27892 KB Output is correct
56 Correct 1046 ms 29768 KB Output is correct
57 Correct 2132 ms 29768 KB Output is correct
58 Correct 1466 ms 50956 KB Output is correct
59 Correct 1255 ms 27800 KB Output is correct
60 Correct 1156 ms 24836 KB Output is correct
61 Execution timed out 5019 ms 29640 KB Time limit exceeded
62 Halted 0 ms 0 KB -