oj.uz

답안 #132999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132999 2019-07-20T03:49:44 Z sebinkim 새 집 (APIO18_new_home) C++14
47 / 100
 5000 ms 985032 KB 
#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

const int sz = 1 << 22;

struct event{
	int t, x, k;
	event(int t, int x, int k) : t(t), x(x), k(k) {}
};

struct line{
	int t, k, x, f;
	line(int t, int k, int x, int f) : t(t), k(k), x(x), f(f) {}
};

struct seg{
	multiset <int> L[sz + 100];
	int T[sz + sz + 100];
	
	seg()
	{
		int i;
		
		for(i=0; i<sz; i++){
			L[i].insert(-1e9);
		}
		
		for(i=0; i<sz+sz; i++){
			T[i] = -1e9;
		}
	}
	
	void insert(int p, int v)
	{
		L[p].insert(v);
		p += sz;
		
		for(; p; p>>=1){
			if(p >= sz) T[p] = *prev(L[p - sz].end());
			else T[p] = max(T[p << 1], T[p << 1 | 1]);
		}
	}
	
	void erase(int p, int v)
	{
		L[p].erase(L[p].find(v));
		p += sz;
		
		for(; p; p>>=1){
			if(p >= sz) T[p] = *prev(L[p - sz].end());
			else T[p] = max(T[p << 1], T[p << 1 | 1]);
		}
	}
	
	int get_max(int l, int r)
	{
		int ret = -1e9;
		l += sz, r += sz;
		
		for(; l<r; ){
			if(l & 1) ret = max(ret, T[l]);
			if(~r & 1) ret = max(ret, T[r]);
			l = l + 1 >> 1;
			r = r - 1 >> 1;
		}
		if(l == r) ret = max(ret, T[l]);
		
		return ret;
	}
};

seg TX, TY;
vector <line> LX, LY;
vector <event> E, Q;
multiset <int> S[303030];
vector <int> X;
int A[303030];
int n, g, q;

void update_line(int t, int k, int x, int f)
{
	if(S[k].empty()){
		LX.eb(t, 0, 1e9, !f);
		LY.eb(t, 2e8, 1e9, !f);
		LX.eb(t, 0, x, f);
		LY.eb(t, 2e8, -x, f);
	}
	else{
		auto it = S[k].lower_bound(x);
		
		if(it == S[k].begin()){
			LX.eb(t, 0, *it, !f);
			LX.eb(t, 0, x, f);
			LX.eb(t, (x + *it) >> 1, *it, f);
			LY.eb(t, (x + *it) >> 1, -x, f);
		}
		else if(it == S[k].end()){
			LY.eb(t, 2e8, -(*prev(it)), !f);
			LY.eb(t, 2e8, -x, f);
			LY.eb(t, (x + *prev(it)) >> 1, -(*prev(it)), f);
			LX.eb(t, (x + *prev(it)) >> 1, x, f);
		}
		else{
			LX.eb(t, (*it + *prev(it)) >> 1, *it, !f);
			LY.eb(t, (*it + *prev(it)) >> 1, -(*prev(it)), !f);
			LX.eb(t, (x + *it) >> 1, *it, f);
			LY.eb(t, (x + *it) >> 1, -x, f);
			LY.eb(t, (x + *prev(it)) >> 1, -(*prev(it)), f);
			LX.eb(t, (x + *prev(it)) >> 1, x, f);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int x, t, a, b, i, j, k, i_, j_, k_;
	
	cin >> n >> g >> q;
	
	for(i=1; i<=n; i++){
		cin >> x >> t >> a >> b;
		E.eb(a, x << 1, t);
		E.eb(b + 1, x << 1, -t);
	}
	
	sort(E.begin(), E.end(), [&](event &ea, event &eb){
		return ea.t < eb.t;
	});
	
	for(i=1; i<=g; i++){
		LX.eb(0, 0, 1e9, 0);
		LY.eb(0, 2e8, 1e9, 0);
	}
	
	for(i=0; i<E.size(); i=i_){
		t = E[i].t;
		for(i_=i; i_<E.size() && E[i_].t == t; i_++){
			k = E[i_].k; x = E[i_].x;
			if(k > 0){
				update_line(t, k, x, 0);
				S[k].insert(x);
			}
			else{
				S[-k].erase(S[-k].find(x));
				update_line(t, -k, x, 1);
			}
		}
	}
	
	for(i=1; i<=q; i++){
		cin >> x >> t;
		x <<= 1; Q.eb(t, x, i);
		X.push_back(x);
	}
	
	sort(Q.begin(), Q.end(), [&](event &ea, event &eb){
		return ea.t < eb.t;
	});
		
	for(line &l: LX) X.push_back(l.k);
	for(line &l: LY) X.push_back(l.k);
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for(line &l: LX) l.k = lower_bound(X.begin(), X.end(), l.k) - X.begin();
	for(line &l: LY) l.k = lower_bound(X.begin(), X.end(), l.k) - X.begin();
	
	for(i=0, j=0, k=0; i<LX.size() || j<LY.size(); i=i_, j=j_, k=k_){
		if(i == LX.size()) t = LY[j].t;
		else if(j == LY.size()) t = LX[i].t;
		else t = min(LX[i].t, LY[j].t);
		
		for(k_=k; k_<Q.size() && Q[k_].t < t; k_++){
			x = lower_bound(X.begin(), X.end(), Q[k_].x) - X.begin();
		 	A[Q[k_].k] = max(TX.get_max(0, x) - Q[k_].x, Q[k_].x + TY.get_max(x, sz - 1));
		}
		
		for(i_=i; i_<LX.size() && LX[i_].t == t; i_++){
			if(!LX[i_].f) TX.insert(LX[i_].k, LX[i_].x);
			else TX.erase(LX[i_].k, LX[i_].x);
		}
		
		for(j_=j; j_<LY.size() && LY[j_].t == t; j_++){
			if(!LY[j_].f) TY.insert(LY[j_].k, LY[j_].x);
			else TY.erase(LY[j_].k, LY[j_].x);
		}
	}
	
	for(; k<Q.size(); k++){
		x = lower_bound(X.begin(), X.end(), Q[k].x) - X.begin();
	 	A[Q[k].k] = max(TX.get_max(0, x) - Q[k].x, Q[k].x + TY.get_max(x, sz - 1));
	}
	
	for(i=1; i<=q; i++){
		if(A[i] >= 2e8) cout << "-1\n";
		else cout << (A[i] >> 1) << "\n";
	}
	
	return 0;
}

Compilation message

new_home.cpp: In member function 'int seg::get_max(int, int)':
new_home.cpp:66:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    l = l + 1 >> 1;
        ~~^~~
new_home.cpp:67:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    r = r - 1 >> 1;
        ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:141:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<E.size(); i=i_){
           ~^~~~~~~~~
new_home.cpp:143:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i_=i; i_<E.size() && E[i_].t == t; i_++){
             ~~^~~~~~~~~
new_home.cpp:175:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0, j=0, k=0; i<LX.size() || j<LY.size(); i=i_, j=j_, k=k_){
                     ~^~~~~~~~~~
new_home.cpp:175:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0, j=0, k=0; i<LX.size() || j<LY.size(); i=i_, j=j_, k=k_){
                                    ~^~~~~~~~~~
new_home.cpp:176:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == LX.size()) t = LY[j].t;
      ~~^~~~~~~~~~~~
new_home.cpp:177:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(j == LY.size()) t = LX[i].t;
           ~~^~~~~~~~~~~~
new_home.cpp:180:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(k_=k; k_<Q.size() && Q[k_].t < t; k_++){
             ~~^~~~~~~~~
new_home.cpp:185:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i_=i; i_<LX.size() && LX[i_].t == t; i_++){
             ~~^~~~~~~~~~
new_home.cpp:190:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j_=j; j_<LY.size() && LY[j_].t == t; j_++){
             ~~^~~~~~~~~~
new_home.cpp:196:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(; k<Q.size(); k++){
        ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1101 ms 868340 KB Output is correct
2 Correct 1103 ms 868416 KB Output is correct
3 Correct 1100 ms 868596 KB Output is correct
4 Correct 1086 ms 868292 KB Output is correct
5 Correct 1099 ms 868596 KB Output is correct
6 Correct 1096 ms 868600 KB Output is correct
7 Correct 1142 ms 868676 KB Output is correct
8 Correct 1117 ms 868548 KB Output is correct
9 Correct 1138 ms 868472 KB Output is correct
10 Correct 1089 ms 868728 KB Output is correct
11 Correct 1087 ms 868348 KB Output is correct
12 Correct 1104 ms 868468 KB Output is correct
13 Correct 1094 ms 868528 KB Output is correct
14 Correct 1089 ms 868536 KB Output is correct
15 Correct 1089 ms 868600 KB Output is correct
16 Correct 1125 ms 868528 KB Output is correct
17 Correct 1092 ms 868488 KB Output is correct
18 Correct 1110 ms 868412 KB Output is correct
19 Correct 1096 ms 868520 KB Output is correct
20 Correct 1091 ms 868600 KB Output is correct
21 Correct 1097 ms 868600 KB Output is correct
22 Correct 1091 ms 868452 KB Output is correct
23 Correct 1112 ms 868556 KB Output is correct
24 Correct 1121 ms 868540 KB Output is correct
25 Correct 1099 ms 868600 KB Output is correct
26 Correct 1102 ms 868600 KB Output is correct
27 Correct 1089 ms 868348 KB Output is correct
28 Correct 1093 ms 868652 KB Output is correct
29 Correct 1121 ms 868472 KB Output is correct
30 Correct 1095 ms 868472 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1101 ms 868340 KB Output is correct
2 Correct 1103 ms 868416 KB Output is correct
3 Correct 1100 ms 868596 KB Output is correct
4 Correct 1086 ms 868292 KB Output is correct
5 Correct 1099 ms 868596 KB Output is correct
6 Correct 1096 ms 868600 KB Output is correct
7 Correct 1142 ms 868676 KB Output is correct
8 Correct 1117 ms 868548 KB Output is correct
9 Correct 1138 ms 868472 KB Output is correct
10 Correct 1089 ms 868728 KB Output is correct
11 Correct 1087 ms 868348 KB Output is correct
12 Correct 1104 ms 868468 KB Output is correct
13 Correct 1094 ms 868528 KB Output is correct
14 Correct 1089 ms 868536 KB Output is correct
15 Correct 1089 ms 868600 KB Output is correct
16 Correct 1125 ms 868528 KB Output is correct
17 Correct 1092 ms 868488 KB Output is correct
18 Correct 1110 ms 868412 KB Output is correct
19 Correct 1096 ms 868520 KB Output is correct
20 Correct 1091 ms 868600 KB Output is correct
21 Correct 1097 ms 868600 KB Output is correct
22 Correct 1091 ms 868452 KB Output is correct
23 Correct 1112 ms 868556 KB Output is correct
24 Correct 1121 ms 868540 KB Output is correct
25 Correct 1099 ms 868600 KB Output is correct
26 Correct 1102 ms 868600 KB Output is correct
27 Correct 1089 ms 868348 KB Output is correct
28 Correct 1093 ms 868652 KB Output is correct
29 Correct 1121 ms 868472 KB Output is correct
30 Correct 1095 ms 868472 KB Output is correct
31 Correct 1826 ms 892808 KB Output is correct
32 Correct 1379 ms 890336 KB Output is correct
33 Correct 1762 ms 891580 KB Output is correct
34 Correct 1786 ms 891328 KB Output is correct
35 Correct 1897 ms 893000 KB Output is correct
36 Correct 1841 ms 892984 KB Output is correct
37 Correct 1611 ms 891464 KB Output is correct
38 Correct 1583 ms 891560 KB Output is correct
39 Correct 1485 ms 891316 KB Output is correct
40 Correct 1499 ms 891580 KB Output is correct
41 Correct 1488 ms 887900 KB Output is correct
42 Correct 1494 ms 887540 KB Output is correct
43 Correct 1296 ms 888272 KB Output is correct
44 Correct 1479 ms 887892 KB Output is correct
45 Correct 1449 ms 888028 KB Output is correct
46 Correct 1419 ms 888020 KB Output is correct
47 Correct 1318 ms 886988 KB Output is correct
48 Correct 1334 ms 887012 KB Output is correct
49 Correct 1367 ms 887460 KB Output is correct
50 Correct 1386 ms 887476 KB Output is correct
51 Correct 1347 ms 887388 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4472 ms 975364 KB Output is correct
2 Execution timed out 5074 ms 985032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5150 ms 980124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1101 ms 868340 KB Output is correct
2 Correct 1103 ms 868416 KB Output is correct
3 Correct 1100 ms 868596 KB Output is correct
4 Correct 1086 ms 868292 KB Output is correct
5 Correct 1099 ms 868596 KB Output is correct
6 Correct 1096 ms 868600 KB Output is correct
7 Correct 1142 ms 868676 KB Output is correct
8 Correct 1117 ms 868548 KB Output is correct
9 Correct 1138 ms 868472 KB Output is correct
10 Correct 1089 ms 868728 KB Output is correct
11 Correct 1087 ms 868348 KB Output is correct
12 Correct 1104 ms 868468 KB Output is correct
13 Correct 1094 ms 868528 KB Output is correct
14 Correct 1089 ms 868536 KB Output is correct
15 Correct 1089 ms 868600 KB Output is correct
16 Correct 1125 ms 868528 KB Output is correct
17 Correct 1092 ms 868488 KB Output is correct
18 Correct 1110 ms 868412 KB Output is correct
19 Correct 1096 ms 868520 KB Output is correct
20 Correct 1091 ms 868600 KB Output is correct
21 Correct 1097 ms 868600 KB Output is correct
22 Correct 1091 ms 868452 KB Output is correct
23 Correct 1112 ms 868556 KB Output is correct
24 Correct 1121 ms 868540 KB Output is correct
25 Correct 1099 ms 868600 KB Output is correct
26 Correct 1102 ms 868600 KB Output is correct
27 Correct 1089 ms 868348 KB Output is correct
28 Correct 1093 ms 868652 KB Output is correct
29 Correct 1121 ms 868472 KB Output is correct
30 Correct 1095 ms 868472 KB Output is correct
31 Correct 1826 ms 892808 KB Output is correct
32 Correct 1379 ms 890336 KB Output is correct
33 Correct 1762 ms 891580 KB Output is correct
34 Correct 1786 ms 891328 KB Output is correct
35 Correct 1897 ms 893000 KB Output is correct
36 Correct 1841 ms 892984 KB Output is correct
37 Correct 1611 ms 891464 KB Output is correct
38 Correct 1583 ms 891560 KB Output is correct
39 Correct 1485 ms 891316 KB Output is correct
40 Correct 1499 ms 891580 KB Output is correct
41 Correct 1488 ms 887900 KB Output is correct
42 Correct 1494 ms 887540 KB Output is correct
43 Correct 1296 ms 888272 KB Output is correct
44 Correct 1479 ms 887892 KB Output is correct
45 Correct 1449 ms 888028 KB Output is correct
46 Correct 1419 ms 888020 KB Output is correct
47 Correct 1318 ms 886988 KB Output is correct
48 Correct 1334 ms 887012 KB Output is correct
49 Correct 1367 ms 887460 KB Output is correct
50 Correct 1386 ms 887476 KB Output is correct
51 Correct 1347 ms 887388 KB Output is correct
52 Correct 1550 ms 889488 KB Output is correct
53 Correct 1513 ms 889524 KB Output is correct
54 Correct 1596 ms 888936 KB Output is correct
55 Correct 1510 ms 887536 KB Output is correct
56 Correct 1499 ms 887692 KB Output is correct
57 Correct 1496 ms 887056 KB Output is correct
58 Correct 1520 ms 887312 KB Output is correct
59 Correct 1492 ms 887476 KB Output is correct
60 Correct 1496 ms 887112 KB Output is correct
61 Correct 1373 ms 889788 KB Output is correct
62 Correct 1533 ms 889524 KB Output is correct
63 Correct 1567 ms 887796 KB Output is correct
64 Correct 1566 ms 887276 KB Output is correct
65 Correct 1555 ms 887132 KB Output is correct
66 Correct 1489 ms 886712 KB Output is correct
67 Correct 1393 ms 886724 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1101 ms 868340 KB Output is correct
2 Correct 1103 ms 868416 KB Output is correct
3 Correct 1100 ms 868596 KB Output is correct
4 Correct 1086 ms 868292 KB Output is correct
5 Correct 1099 ms 868596 KB Output is correct
6 Correct 1096 ms 868600 KB Output is correct
7 Correct 1142 ms 868676 KB Output is correct
8 Correct 1117 ms 868548 KB Output is correct
9 Correct 1138 ms 868472 KB Output is correct
10 Correct 1089 ms 868728 KB Output is correct
11 Correct 1087 ms 868348 KB Output is correct
12 Correct 1104 ms 868468 KB Output is correct
13 Correct 1094 ms 868528 KB Output is correct
14 Correct 1089 ms 868536 KB Output is correct
15 Correct 1089 ms 868600 KB Output is correct
16 Correct 1125 ms 868528 KB Output is correct
17 Correct 1092 ms 868488 KB Output is correct
18 Correct 1110 ms 868412 KB Output is correct
19 Correct 1096 ms 868520 KB Output is correct
20 Correct 1091 ms 868600 KB Output is correct
21 Correct 1097 ms 868600 KB Output is correct
22 Correct 1091 ms 868452 KB Output is correct
23 Correct 1112 ms 868556 KB Output is correct
24 Correct 1121 ms 868540 KB Output is correct
25 Correct 1099 ms 868600 KB Output is correct
26 Correct 1102 ms 868600 KB Output is correct
27 Correct 1089 ms 868348 KB Output is correct
28 Correct 1093 ms 868652 KB Output is correct
29 Correct 1121 ms 868472 KB Output is correct
30 Correct 1095 ms 868472 KB Output is correct
31 Correct 1826 ms 892808 KB Output is correct
32 Correct 1379 ms 890336 KB Output is correct
33 Correct 1762 ms 891580 KB Output is correct
34 Correct 1786 ms 891328 KB Output is correct
35 Correct 1897 ms 893000 KB Output is correct
36 Correct 1841 ms 892984 KB Output is correct
37 Correct 1611 ms 891464 KB Output is correct
38 Correct 1583 ms 891560 KB Output is correct
39 Correct 1485 ms 891316 KB Output is correct
40 Correct 1499 ms 891580 KB Output is correct
41 Correct 1488 ms 887900 KB Output is correct
42 Correct 1494 ms 887540 KB Output is correct
43 Correct 1296 ms 888272 KB Output is correct
44 Correct 1479 ms 887892 KB Output is correct
45 Correct 1449 ms 888028 KB Output is correct
46 Correct 1419 ms 888020 KB Output is correct
47 Correct 1318 ms 886988 KB Output is correct
48 Correct 1334 ms 887012 KB Output is correct
49 Correct 1367 ms 887460 KB Output is correct
50 Correct 1386 ms 887476 KB Output is correct
51 Correct 1347 ms 887388 KB Output is correct
52 Correct 4472 ms 975364 KB Output is correct
53 Execution timed out 5074 ms 985032 KB Time limit exceeded
54 Halted 0 ms 0 KB -