oj.uz

답안 #545632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545632 2022-04-05T04:17:35 Z 8e7 새 집 (APIO18_new_home) C++17
0 / 100
 5000 ms 208760 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) 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) 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->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;});
	sort(rev.begin(), rev.end(), [&] (event x, event y){return 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:98:3: note: in expansion of macro 'debug'
   98 |   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:102:4: note: in expansion of macro 'debug'
  102 |    debug("seg", l, r, u, d);
      |    ^~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:148:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   while (lid < lev.size() && lev[lid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~
new_home.cpp:152:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   while (rid < rev.size() && rev[rid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 123568 KB Output is correct
2 Correct 54 ms 123584 KB Output is correct
3 Correct 57 ms 123528 KB Output is correct
4 Correct 61 ms 123580 KB Output is correct
5 Execution timed out 5094 ms 123724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 123568 KB Output is correct
2 Correct 54 ms 123584 KB Output is correct
3 Correct 57 ms 123528 KB Output is correct
4 Correct 61 ms 123580 KB Output is correct
5 Execution timed out 5094 ms 123724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 123568 KB Output is correct
2 Correct 54 ms 123584 KB Output is correct
3 Correct 57 ms 123528 KB Output is correct
4 Correct 61 ms 123580 KB Output is correct
5 Execution timed out 5094 ms 123724 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 123568 KB Output is correct
2 Correct 54 ms 123584 KB Output is correct
3 Correct 57 ms 123528 KB Output is correct
4 Correct 61 ms 123580 KB Output is correct
5 Execution timed out 5094 ms 123724 KB Time limit exceeded
6 Halted 0 ms 0 KB -