oj.uz

Submission #112029

# Submission time Handle Problem Language Result Execution time Memory
112029 2019-05-17T05:54:01 Z ecasdqina New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 16988 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...));
}

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 == begin(st)) return std::abs((*it).first - t);
		return std::min(std::abs((*it).first - t), std::abs((*(--it)).first - t));
	};
	
	std::vector<int> ans(q, -1);
	if(n <= 400 and q <= 400 and false) {
		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});
			}
			
			/*
			cout << "YEAR: " << Y << endl;
			for(int k = 0; k < K; k++) {
				cout << k << ": ";
				for(auto v: vec[k]) cout << v.second + 1 << " ";
				cout << endl;
			}
			cout << endl;
			*/
			
			int ret = 0;
			for(int k = 0; k < K; k++) {
				if(vec[k].empty()) {
					ret = -1;
					break;
				}
				
				int mi = 1 << 30;
				for(auto amber: vec[k]) mi = std::min(mi, std::abs(amber.first - L));
				ret = std::max(ret, mi);
			//	ret = std::max(ret, calcDist(vec[k], L));
			}
			ans[YYS.second] = ret;
		}
	} else {
		assert(0);
	}
	for(auto v: ans) printf("%d\n", v);
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curA < A.size() and A[curA].first <= Y) {
          ~~~~~^~~~~~~~~~
new_home.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curB < B.size() and B[curB].first <= Y) {
          ~~~~~^~~~~~~~~~
new_home.cpp:17: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:20: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:22: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 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 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 4 ms 384 KB Output is correct
20 Correct 2 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 4 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 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 4 ms 384 KB Output is correct
20 Correct 2 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 4 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Execution timed out 5089 ms 5036 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 16988 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 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 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 4 ms 384 KB Output is correct
20 Correct 2 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 4 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Execution timed out 5089 ms 5036 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 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 4 ms 384 KB Output is correct
20 Correct 2 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 4 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Execution timed out 5089 ms 5036 KB Time limit exceeded
32 Halted 0 ms 0 KB -