Submission #545664

#	Time	Username	Problem	Language	Result	Execution time	Memory
545664		8e7	New Home (APIO18_new_home)	C++17	100 / 100	1426 ms	100332 KiB

new_home

//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;
	event(){x = val = l = r = 0;}
	event(int a, int b, int c, int d){x = a, val = b, l = c, r = d;}
};
vector<event> lev, rev;
struct segtree{
	int type; //1: max, 0:min
	int seg[4*maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (type == 0) seg[cur] = inf;
		if (r - l == 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
	}
	void modify(int cur, int l, int r, int ql, int qr, int v) {
		if (r <= l || ql >= r || qr <= l || qr == ql) return;
		if (ql <= l && qr >= r) {
			if (type) seg[cur] = max(seg[cur], v);
			else seg[cur] = min(seg[cur], v);
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v);
		modify(cur*2+1, m, r, ql, qr, v);
	}	
	int query(int cur, int l, int r, int ind) {
		if (r <= l || ind >= r || ind < l) return type ? -inf : inf;
		int val = seg[cur];
		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;
 
		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(m-1, l, u, d));
			rev.push_back(event(m, r, u, d));
		};
		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;});
	sort(rev.begin(), rev.end(), [&] (event x, event y){return x.x < y.x;});
 
	int lid = 0, rid = 0;
	rtr.type = 1;
	ltr.init(1, 0, q);
	for (int i = 0;i < q;i++) {
		query cur = que[i];
		while (rid < rev.size() && rev[rid].x <= cur.x) {
			rtr.modify(1, 0, q, rev[rid].l, rev[rid].r, rev[rid].val);
			rid++;
		}
		ans[cur.id] = rtr.query(1, 0, q, cur.ti) - cur.x;		
	}
	for (int i = q - 1;i >= 0;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);
			lid++;
		}
		ans[cur.id] = max(ans[cur.id], cur.x - ltr.query(1, 0, q, cur.ti));
	}
	for (int i = 0;i < q;i++) {
		cout << (ans[i] >= inf/2 ? -1 : ans[i]) << "\n";
	}
}

Compilation message (stderr)

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:106:4: note: in expansion of macro 'debug'
  106 |    debug("seg", l, r, u, d);
      |    ^~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:151:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |   while (rid < rev.size() && rev[rid].x <= cur.x) {
      |          ~~~~^~~~~~~~~~~~
new_home.cpp:159:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |   while (lid < lev.size() && lev[lid].x >= cur.x) {
      |          ~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20