oj.uz

Submission #545647

# Submission time Handle Problem Language Result Execution time Memory
545647 2022-04-05T05:12:29 Z 8e7 New Home (APIO18_new_home) C++17
5 / 100
 88 ms 8264 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 405
#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;
		for (int i = ql;i < qr;i++) {
			if (ch == 1) seg[i].insert(v);
			else seg[i].erase(seg[i].find(v));
		}
		/*
		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;
		if (seg[ind].size()) return (type ? *prev(seg[ind].end()) : *seg[ind].begin());
		else 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:108:3: note: in expansion of macro 'debug'
  108 |   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:112:4: note: in expansion of macro 'debug'
  112 |    debug("seg", l, r, u, d);
      |    ^~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:158:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |   while (lid < lev.size() && lev[lid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~
new_home.cpp:162:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |   while (rid < rev.size() && rev[rid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 76 ms 8160 KB Output is correct
8 Correct 37 ms 3164 KB Output is correct
9 Correct 88 ms 8148 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 27 ms 3464 KB Output is correct
16 Correct 48 ms 4812 KB Output is correct
17 Correct 11 ms 1784 KB Output is correct
18 Correct 32 ms 3592 KB Output is correct
19 Correct 47 ms 4920 KB Output is correct
20 Correct 15 ms 1896 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 81 ms 8264 KB Output is correct
23 Correct 44 ms 4628 KB Output is correct
24 Correct 29 ms 3180 KB Output is correct
25 Correct 11 ms 1484 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 764 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 76 ms 8160 KB Output is correct
8 Correct 37 ms 3164 KB Output is correct
9 Correct 88 ms 8148 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 27 ms 3464 KB Output is correct
16 Correct 48 ms 4812 KB Output is correct
17 Correct 11 ms 1784 KB Output is correct
18 Correct 32 ms 3592 KB Output is correct
19 Correct 47 ms 4920 KB Output is correct
20 Correct 15 ms 1896 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 81 ms 8264 KB Output is correct
23 Correct 44 ms 4628 KB Output is correct
24 Correct 29 ms 3180 KB Output is correct
25 Correct 11 ms 1484 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 764 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Runtime error 27 ms 5508 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 76 ms 8160 KB Output is correct
8 Correct 37 ms 3164 KB Output is correct
9 Correct 88 ms 8148 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 27 ms 3464 KB Output is correct
16 Correct 48 ms 4812 KB Output is correct
17 Correct 11 ms 1784 KB Output is correct
18 Correct 32 ms 3592 KB Output is correct
19 Correct 47 ms 4920 KB Output is correct
20 Correct 15 ms 1896 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 81 ms 8264 KB Output is correct
23 Correct 44 ms 4628 KB Output is correct
24 Correct 29 ms 3180 KB Output is correct
25 Correct 11 ms 1484 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 764 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Runtime error 27 ms 5508 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 76 ms 8160 KB Output is correct
8 Correct 37 ms 3164 KB Output is correct
9 Correct 88 ms 8148 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 27 ms 3464 KB Output is correct
16 Correct 48 ms 4812 KB Output is correct
17 Correct 11 ms 1784 KB Output is correct
18 Correct 32 ms 3592 KB Output is correct
19 Correct 47 ms 4920 KB Output is correct
20 Correct 15 ms 1896 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 81 ms 8264 KB Output is correct
23 Correct 44 ms 4628 KB Output is correct
24 Correct 29 ms 3180 KB Output is correct
25 Correct 11 ms 1484 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 764 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Runtime error 27 ms 5508 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -