oj.uz

Submission #545648

# Submission time Handle Problem Language Result Execution time Memory
545648 2022-04-05T05:13:02 Z 8e7 New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 259524 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 2e8;
struct store{
	int x, a, b;
	store(){x = a = b = 0;}
	store(int u, int v, int w){x = u, a = v, b = w;}
};
vector<store> seg[maxn];

struct query{
	int x, ti, id;
	query(){x = ti = id = 0;}
} que[maxn];

int ans[maxn];
struct event{
	int x, val, l, r, ch;
	event(){x = val = l = r = ch = 0;}
	event(int a, int b, int c, int d, int e){x = a, val = b, l = c, r = d, ch = e;}
};
vector<event> lev, rev;
struct segtree{
	int type; //1: max, 0:min
	multiset<int> seg[4*maxn];
	void modify(int cur, int l, int r, int ql, int qr, int v, int ch) {
		if (r <= l || ql >= r || qr <= l || qr == ql) return;
		
		if (ql <= l && qr >= r) {
			if (ch == 1) seg[cur].insert(v);
			else seg[cur].erase(seg[cur].find(v));
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v, ch);
		modify(cur*2+1, m, r, ql, qr, v, ch);
	}	
	int query(int cur, int l, int r, int ind) {
		if (r <= l || ind >= r || ind < l) return type ? -inf : inf;
		int val;
		if (type) val = (seg[cur].size() ? *prev(seg[cur].end()) : -inf);
		else val = (seg[cur].size() ? *seg[cur].begin() : inf);
		if (r - l == 1) return val;
		int m = (l + r) / 2, rec;
		if (ind < m) rec = query(cur*2, l, m, ind);
		else rec = query(cur*2+1, m, r, ind);
		return type ? max(val, rec) : min(val, rec);
	}	
} ltr, rtr;


int main() {
	io
	int n, k, q;
	cin >> n >> k >> q;
	vector<int> tv;
	for (int i = 1;i <= k;i++) seg[i].push_back(store(-inf, 0, inf));
	for (int i = 0;i < n;i++) {
		store s;
		int ty;
		cin >> s.x >> ty >> s.a >> s.b;		
		s.b++;
		//tv.push_back(s.a), tv.push_back(s.b);	
		seg[ty].push_back(s);
	}
	for (int i = 1;i <= k;i++) seg[i].push_back(store(inf, 0, inf));
	for (int i = 0;i < q;i++) {
		cin >> que[i].x >> que[i].ti;
		que[i].id = i;
		tv.push_back(que[i].ti);
	}
	sort(tv.begin(), tv.end());
	tv.resize(int(unique(tv.begin(), tv.end()) - tv.begin()));
	//pary(tv.begin(), tv.end());
	auto conv = [&] (int x){
		return lower_bound(tv.begin(), tv.end(), x) - tv.begin();
	};
	for (int i = 1;i <= k;i++) {
		set<pii> se;

		debug("type", i);
		auto add_seg = [&] (int l, int r, int u, int d) {
			if (d <= u) return;
			int m = (l + r + 1) / 2;	
			debug("seg", l, r, u, d);
			lev.push_back(event(l, l, u, d, 1));
			lev.push_back(event(m, l, u, d, -1));
			rev.push_back(event(m, r, u, d, 1));
			rev.push_back(event(r, r, u, d, -1));
		};
		sort(seg[i].begin(), seg[i].end(), [&] (store x, store y){return x.x < y.x;});
		for (auto &p:seg[i]) {
			p.a = conv(p.a), p.b = conv(p.b);	
			if (se.empty()) {
				se.insert({p.a, p.x});
				se.insert({p.b+1, p.x});
			} else {
				if (p.a == p.b) continue;
				auto it = se.lower_bound(make_pair(p.a, -inf));	
				int cur = p.a;
				while (it != se.end() && it->ff <= p.b) {
					if (it != se.begin()) add_seg(prev(it)->ss, p.x, cur, it->ff);
					cur = it->ff;
					it = next(it);
				}
				if (it != se.begin()) add_seg(prev(it)->ss, p.x, cur, p.b);

				it = se.lower_bound(make_pair(p.a, -inf));
				int last = prev(it)->ss;
				while (it != se.end() && it->ff < p.b) {
					last = it->ss;	
					se.erase(it);
					it = se.lower_bound(make_pair(p.a, -inf));
				}
				se.insert(make_pair(p.a, p.x));
				if (it->ff > p.b) {
					se.insert(make_pair(p.b, last));	
				}
			}
		}	
	}
	for (int i = 0;i < q;i++) que[i].ti = conv(que[i].ti);	
	sort(que, que + q, [&] (query x, query y){return x.x < y.x;});		
	sort(lev.begin(), lev.end(), [&] (event x, event y){return x.x == y.x ? x.ch > y.ch : x.x < y.x;});
	sort(rev.begin(), rev.end(), [&] (event x, event y){return x.x == y.x ? x.ch > y.ch : x.x < y.x;});

	int lid = 0, rid = 0;
	rtr.type = 1;
	for (int i = 0;i < q;i++) {
		query cur = que[i];
		while (lid < lev.size() && lev[lid].x <= cur.x) {
			ltr.modify(1, 0, q, lev[lid].l, lev[lid].r, lev[lid].val, lev[lid].ch);
			lid++;
		}
		while (rid < rev.size() && rev[rid].x <= cur.x) {
			rtr.modify(1, 0, q, rev[rid].l, rev[rid].r, rev[rid].val, rev[rid].ch);
			rid++;
		}
		ans[cur.id] = max(cur.x - ltr.query(1, 0, q, cur.ti), rtr.query(1, 0, q, cur.ti) - cur.x);		
	}
	for (int i = 0;i < q;i++) {
		cout << (ans[i] >= inf/2 ? -1 : ans[i]) << "\n";
	}
}
/*

*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
new_home.cpp:99:3: note: in expansion of macro 'debug'
   99 |   debug("type", i);
      |   ^~~~~
new_home.cpp: In lambda function:
new_home.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
new_home.cpp:103:4: note: in expansion of macro 'debug'
  103 |    debug("seg", l, r, u, d);
      |    ^~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:149:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   while (lid < lev.size() && lev[lid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~
new_home.cpp:153:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   while (rid < rev.size() && rev[rid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 123496 KB Output is correct
2 Correct 64 ms 123552 KB Output is correct
3 Correct 54 ms 123504 KB Output is correct
4 Correct 54 ms 123596 KB Output is correct
5 Correct 60 ms 123720 KB Output is correct
6 Correct 63 ms 123812 KB Output is correct
7 Correct 59 ms 124016 KB Output is correct
8 Correct 59 ms 123808 KB Output is correct
9 Correct 57 ms 123964 KB Output is correct
10 Correct 60 ms 123728 KB Output is correct
11 Correct 60 ms 123724 KB Output is correct
12 Correct 65 ms 123732 KB Output is correct
13 Correct 55 ms 123744 KB Output is correct
14 Correct 57 ms 123728 KB Output is correct
15 Correct 60 ms 123888 KB Output is correct
16 Correct 61 ms 123848 KB Output is correct
17 Correct 65 ms 123872 KB Output is correct
18 Correct 64 ms 123916 KB Output is correct
19 Correct 58 ms 123856 KB Output is correct
20 Correct 66 ms 123748 KB Output is correct
21 Correct 58 ms 123656 KB Output is correct
22 Correct 61 ms 124040 KB Output is correct
23 Correct 60 ms 123980 KB Output is correct
24 Correct 58 ms 123852 KB Output is correct
25 Correct 56 ms 123748 KB Output is correct
26 Correct 58 ms 123828 KB Output is correct
27 Correct 59 ms 123760 KB Output is correct
28 Correct 69 ms 123812 KB Output is correct
29 Correct 58 ms 123648 KB Output is correct
30 Correct 57 ms 123660 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 123496 KB Output is correct
2 Correct 64 ms 123552 KB Output is correct
3 Correct 54 ms 123504 KB Output is correct
4 Correct 54 ms 123596 KB Output is correct
5 Correct 60 ms 123720 KB Output is correct
6 Correct 63 ms 123812 KB Output is correct
7 Correct 59 ms 124016 KB Output is correct
8 Correct 59 ms 123808 KB Output is correct
9 Correct 57 ms 123964 KB Output is correct
10 Correct 60 ms 123728 KB Output is correct
11 Correct 60 ms 123724 KB Output is correct
12 Correct 65 ms 123732 KB Output is correct
13 Correct 55 ms 123744 KB Output is correct
14 Correct 57 ms 123728 KB Output is correct
15 Correct 60 ms 123888 KB Output is correct
16 Correct 61 ms 123848 KB Output is correct
17 Correct 65 ms 123872 KB Output is correct
18 Correct 64 ms 123916 KB Output is correct
19 Correct 58 ms 123856 KB Output is correct
20 Correct 66 ms 123748 KB Output is correct
21 Correct 58 ms 123656 KB Output is correct
22 Correct 61 ms 124040 KB Output is correct
23 Correct 60 ms 123980 KB Output is correct
24 Correct 58 ms 123852 KB Output is correct
25 Correct 56 ms 123748 KB Output is correct
26 Correct 58 ms 123828 KB Output is correct
27 Correct 59 ms 123760 KB Output is correct
28 Correct 69 ms 123812 KB Output is correct
29 Correct 58 ms 123648 KB Output is correct
30 Correct 57 ms 123660 KB Output is correct
31 Correct 1704 ms 144440 KB Output is correct
32 Correct 274 ms 136436 KB Output is correct
33 Correct 762 ms 143300 KB Output is correct
34 Correct 1679 ms 147616 KB Output is correct
35 Correct 1205 ms 143692 KB Output is correct
36 Correct 813 ms 143400 KB Output is correct
37 Correct 692 ms 143240 KB Output is correct
38 Correct 610 ms 142944 KB Output is correct
39 Correct 503 ms 143148 KB Output is correct
40 Correct 479 ms 143064 KB Output is correct
41 Correct 2210 ms 168932 KB Output is correct
42 Correct 2335 ms 169900 KB Output is correct
43 Correct 120 ms 133248 KB Output is correct
44 Correct 2031 ms 167836 KB Output is correct
45 Correct 1388 ms 161192 KB Output is correct
46 Correct 659 ms 149456 KB Output is correct
47 Correct 441 ms 149472 KB Output is correct
48 Correct 348 ms 145664 KB Output is correct
49 Correct 521 ms 151324 KB Output is correct
50 Correct 957 ms 162240 KB Output is correct
51 Correct 479 ms 148304 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 123496 KB Output is correct
2 Correct 64 ms 123552 KB Output is correct
3 Correct 54 ms 123504 KB Output is correct
4 Correct 54 ms 123596 KB Output is correct
5 Correct 60 ms 123720 KB Output is correct
6 Correct 63 ms 123812 KB Output is correct
7 Correct 59 ms 124016 KB Output is correct
8 Correct 59 ms 123808 KB Output is correct
9 Correct 57 ms 123964 KB Output is correct
10 Correct 60 ms 123728 KB Output is correct
11 Correct 60 ms 123724 KB Output is correct
12 Correct 65 ms 123732 KB Output is correct
13 Correct 55 ms 123744 KB Output is correct
14 Correct 57 ms 123728 KB Output is correct
15 Correct 60 ms 123888 KB Output is correct
16 Correct 61 ms 123848 KB Output is correct
17 Correct 65 ms 123872 KB Output is correct
18 Correct 64 ms 123916 KB Output is correct
19 Correct 58 ms 123856 KB Output is correct
20 Correct 66 ms 123748 KB Output is correct
21 Correct 58 ms 123656 KB Output is correct
22 Correct 61 ms 124040 KB Output is correct
23 Correct 60 ms 123980 KB Output is correct
24 Correct 58 ms 123852 KB Output is correct
25 Correct 56 ms 123748 KB Output is correct
26 Correct 58 ms 123828 KB Output is correct
27 Correct 59 ms 123760 KB Output is correct
28 Correct 69 ms 123812 KB Output is correct
29 Correct 58 ms 123648 KB Output is correct
30 Correct 57 ms 123660 KB Output is correct
31 Correct 1704 ms 144440 KB Output is correct
32 Correct 274 ms 136436 KB Output is correct
33 Correct 762 ms 143300 KB Output is correct
34 Correct 1679 ms 147616 KB Output is correct
35 Correct 1205 ms 143692 KB Output is correct
36 Correct 813 ms 143400 KB Output is correct
37 Correct 692 ms 143240 KB Output is correct
38 Correct 610 ms 142944 KB Output is correct
39 Correct 503 ms 143148 KB Output is correct
40 Correct 479 ms 143064 KB Output is correct
41 Correct 2210 ms 168932 KB Output is correct
42 Correct 2335 ms 169900 KB Output is correct
43 Correct 120 ms 133248 KB Output is correct
44 Correct 2031 ms 167836 KB Output is correct
45 Correct 1388 ms 161192 KB Output is correct
46 Correct 659 ms 149456 KB Output is correct
47 Correct 441 ms 149472 KB Output is correct
48 Correct 348 ms 145664 KB Output is correct
49 Correct 521 ms 151324 KB Output is correct
50 Correct 957 ms 162240 KB Output is correct
51 Correct 479 ms 148304 KB Output is correct
52 Execution timed out 5088 ms 259524 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 123496 KB Output is correct
2 Correct 64 ms 123552 KB Output is correct
3 Correct 54 ms 123504 KB Output is correct
4 Correct 54 ms 123596 KB Output is correct
5 Correct 60 ms 123720 KB Output is correct
6 Correct 63 ms 123812 KB Output is correct
7 Correct 59 ms 124016 KB Output is correct
8 Correct 59 ms 123808 KB Output is correct
9 Correct 57 ms 123964 KB Output is correct
10 Correct 60 ms 123728 KB Output is correct
11 Correct 60 ms 123724 KB Output is correct
12 Correct 65 ms 123732 KB Output is correct
13 Correct 55 ms 123744 KB Output is correct
14 Correct 57 ms 123728 KB Output is correct
15 Correct 60 ms 123888 KB Output is correct
16 Correct 61 ms 123848 KB Output is correct
17 Correct 65 ms 123872 KB Output is correct
18 Correct 64 ms 123916 KB Output is correct
19 Correct 58 ms 123856 KB Output is correct
20 Correct 66 ms 123748 KB Output is correct
21 Correct 58 ms 123656 KB Output is correct
22 Correct 61 ms 124040 KB Output is correct
23 Correct 60 ms 123980 KB Output is correct
24 Correct 58 ms 123852 KB Output is correct
25 Correct 56 ms 123748 KB Output is correct
26 Correct 58 ms 123828 KB Output is correct
27 Correct 59 ms 123760 KB Output is correct
28 Correct 69 ms 123812 KB Output is correct
29 Correct 58 ms 123648 KB Output is correct
30 Correct 57 ms 123660 KB Output is correct
31 Correct 1704 ms 144440 KB Output is correct
32 Correct 274 ms 136436 KB Output is correct
33 Correct 762 ms 143300 KB Output is correct
34 Correct 1679 ms 147616 KB Output is correct
35 Correct 1205 ms 143692 KB Output is correct
36 Correct 813 ms 143400 KB Output is correct
37 Correct 692 ms 143240 KB Output is correct
38 Correct 610 ms 142944 KB Output is correct
39 Correct 503 ms 143148 KB Output is correct
40 Correct 479 ms 143064 KB Output is correct
41 Correct 2210 ms 168932 KB Output is correct
42 Correct 2335 ms 169900 KB Output is correct
43 Correct 120 ms 133248 KB Output is correct
44 Correct 2031 ms 167836 KB Output is correct
45 Correct 1388 ms 161192 KB Output is correct
46 Correct 659 ms 149456 KB Output is correct
47 Correct 441 ms 149472 KB Output is correct
48 Correct 348 ms 145664 KB Output is correct
49 Correct 521 ms 151324 KB Output is correct
50 Correct 957 ms 162240 KB Output is correct
51 Correct 479 ms 148304 KB Output is correct
52 Execution timed out 5057 ms 193076 KB Time limit exceeded
53 Halted 0 ms 0 KB -