oj.uz

Submission #103908

# Submission time Handle Problem Language Result Execution time Memory
103908 2019-04-03T08:28:30 Z dupreez New Home (APIO18_new_home) C++14
12 / 100
 4578 ms 14176 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <cstdio>
#include <cmath>
#include <bitset>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;

const ll MOD = 1000000007, N =60010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -7230040172838, MAX = 7230040172838;
const int S = 60;
ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
static ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}

ll pw(ll v1, ll v2) {
	ll v3 = 1;
	while (v2 > 0) {
		if (v2 % 2)v3 = (v3*v1) % MOD;
		v1 = (v1*v1) % MOD;
		v2 /= 2;
	}
	return v3;
}

int n, q, as[N], k, sid = 1,sid2=1;
pair<int, pos> si[N],sd[N];
pair<pos, int> qr[N];
multiset<int> l1[410], l2[410];

int main() {
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) {
		int v1, v2, v3, v4;
		cin >> v1 >> v2 >> v3 >> v4;
		si[i] = mk(v3, mk(v1, v2));
		sd[i] = mk(v4, mk(v1, v2));
	}
	sort(si + 1, si + n + 1);
	sort(sd + 1, sd + n + 1);
	for (int i = 0; i < q; i++) { cin >> qr[i].first.second >> qr[i].first.first; qr[i].second = i; }
	sort(qr, qr + q);
	for (int i = 0; i < q; i++) {
		ll xi = qr[i].first.second,tv=qr[i].first.first;
		ll cv = -1;
		
		for (; sid <= n && si[sid].first <= tv; sid++) {
			int v1 = si[sid].second.first, v2 = si[sid].second.second;
			l1[v2].insert(v1);			
			l2[v2].insert(-v1);			
		}

		for (; sid2 <= n && sd[sid2].first < tv; sid2++) {
			int v1 = sd[sid2].second.first, v2 = sd[sid2].second.second;
			l1[v2].erase(l1[v2].find(v1));			
			l2[v2].erase(l2[v2].find(-v1));
		}

		for (int j = 1; j <= k; j++) {
			if (l1[j].empty()) { cv = -1; break; }
			auto v1 = l1[j].lower_bound(xi), v2 = l2[j].lower_bound(-xi);
			ll cv2 = MAX;
			if (v1 != l1[j].end()) { cv2 = min(cv2, abs(*v1 - xi)); }
			if (v2 != l2[j].end()) { cv2 = min(cv2, abs(-*v2 - xi)); }
			cv = max(cv, cv2);
		}
		as[qr[i].second] = cv;
	}
	for (int i = 0; i < q; i++)cout << as[i] << endl;
	return 0;
}

Compilation message

new_home.cpp: In function 'll gcd(ll, ll)':
new_home.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
  ^~
new_home.cpp:27:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
                         ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 6 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 4578 ms 13952 KB Output is correct
32 Correct 232 ms 8540 KB Output is correct
33 Correct 572 ms 10332 KB Output is correct
34 Correct 3243 ms 10452 KB Output is correct
35 Correct 2568 ms 13828 KB Output is correct
36 Correct 836 ms 13816 KB Output is correct
37 Correct 476 ms 8580 KB Output is correct
38 Correct 312 ms 8440 KB Output is correct
39 Correct 317 ms 8188 KB Output is correct
40 Correct 336 ms 8160 KB Output is correct
41 Correct 499 ms 8380 KB Output is correct
42 Correct 405 ms 8228 KB Output is correct
43 Correct 4064 ms 13520 KB Output is correct
44 Correct 439 ms 8228 KB Output is correct
45 Correct 332 ms 8256 KB Output is correct
46 Correct 251 ms 8184 KB Output is correct
47 Correct 232 ms 7800 KB Output is correct
48 Correct 269 ms 7672 KB Output is correct
49 Correct 313 ms 7928 KB Output is correct
50 Correct 410 ms 8272 KB Output is correct
51 Correct 237 ms 7928 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 240 ms 14176 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 269 ms 13776 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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 6 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 4578 ms 13952 KB Output is correct
32 Correct 232 ms 8540 KB Output is correct
33 Correct 572 ms 10332 KB Output is correct
34 Correct 3243 ms 10452 KB Output is correct
35 Correct 2568 ms 13828 KB Output is correct
36 Correct 836 ms 13816 KB Output is correct
37 Correct 476 ms 8580 KB Output is correct
38 Correct 312 ms 8440 KB Output is correct
39 Correct 317 ms 8188 KB Output is correct
40 Correct 336 ms 8160 KB Output is correct
41 Correct 499 ms 8380 KB Output is correct
42 Correct 405 ms 8228 KB Output is correct
43 Correct 4064 ms 13520 KB Output is correct
44 Correct 439 ms 8228 KB Output is correct
45 Correct 332 ms 8256 KB Output is correct
46 Correct 251 ms 8184 KB Output is correct
47 Correct 232 ms 7800 KB Output is correct
48 Correct 269 ms 7672 KB Output is correct
49 Correct 313 ms 7928 KB Output is correct
50 Correct 410 ms 8272 KB Output is correct
51 Correct 237 ms 7928 KB Output is correct
52 Runtime error 181 ms 12032 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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 6 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 512 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 4578 ms 13952 KB Output is correct
32 Correct 232 ms 8540 KB Output is correct
33 Correct 572 ms 10332 KB Output is correct
34 Correct 3243 ms 10452 KB Output is correct
35 Correct 2568 ms 13828 KB Output is correct
36 Correct 836 ms 13816 KB Output is correct
37 Correct 476 ms 8580 KB Output is correct
38 Correct 312 ms 8440 KB Output is correct
39 Correct 317 ms 8188 KB Output is correct
40 Correct 336 ms 8160 KB Output is correct
41 Correct 499 ms 8380 KB Output is correct
42 Correct 405 ms 8228 KB Output is correct
43 Correct 4064 ms 13520 KB Output is correct
44 Correct 439 ms 8228 KB Output is correct
45 Correct 332 ms 8256 KB Output is correct
46 Correct 251 ms 8184 KB Output is correct
47 Correct 232 ms 7800 KB Output is correct
48 Correct 269 ms 7672 KB Output is correct
49 Correct 313 ms 7928 KB Output is correct
50 Correct 410 ms 8272 KB Output is correct
51 Correct 237 ms 7928 KB Output is correct
52 Runtime error 240 ms 14176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -