oj.uz

Submission #414379

# Submission time Handle Problem Language Result Execution time Memory
414379 2021-05-30T11:45:09 Z hhhhaura New Home (APIO18_new_home) C++14
0 / 100
 3167 ms 677000 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define INF 1e9
using namespace std;
#define pii pair<int, int>
namespace seg {
	const int P = 5e7;
	int p = 0, root = 0;
	vector<int> lch, rch, seg;
	int get_new() {return ++p;}
	void init_() {
		lch.assign(P, 0);
		rch.assign(P, 0);
		seg.assign(P, INF);
		root = get_new();
	}
	void pull(int nd) {
		seg[nd] = min(seg[lch[nd]], seg[rch[nd]]);
	}
	void modify(int nd, int L, int R, int x, int v) {
		if(L == R) seg[nd] = v;
		else {
			int mid = (L + R) / 2;
			if(!lch[nd]) lch[nd] = get_new();
			if(!rch[nd]) rch[nd] = get_new();
			if(x <= mid) modify(lch[nd], L, mid, x, v);
			else modify(rch[nd], mid + 1, R, x, v);
			pull(nd); 
		}
	}
/*	int query(int nd, int L, int R, int l, int r) {
		if(!nd) return INF;
		else if(l <= L && r >= R) return seg[nd];
		else {
			int mid = (L + R) / 2;
			return min(query(lch[nd], L, mid, l, r),
				query(rch[nd], mid + 1, R, l, r));
		}
	}
*/
	int get_lb(int nd, int L, int R, int x, int cur) {
		int mid = (L + R) / 2;
		if(L == R || !nd) {
			int l = 2 * x - L;
			if(L == INF || cur < l) return -1;
			else return abs(max(x, L) - x);
		}
		else {
			int mid = (L + R) / 2, l = 2 * x - mid;
			if(min(cur, seg[rch[nd]]) >= l) 
				return get_lb(lch[nd], L, mid, x, min(cur, seg[rch[nd]]));
			else return get_lb(rch[nd], mid + 1, R, x, cur);
		}
	}

/*	int ask(int x) {
		return query(root, 1, INF, x, INF);
	}
*/	int answer(int x) {
		return get_lb(root, 1, INF, x, INF);
	}
	void change(int x, int v) {
		modify(root, 1, INF, x, v);
	}
};
namespace solver {
	int n, k, q;
	struct query {
		int x, tp, id;
		bool operator<(query b) {
			if(x != b.x) return x < b.x;
			else return tp < b.tp;
		}
	};
	vector<map<int, int>> s;
	vector<multiset<pii>> cur;
	vector<pii> ans, stores;
	vector<query> qq;
	vector<int> v;
	void init_(int _n, int _k, int _q) {
		n = _n, k = _k, q = _q;
		s.assign(k + 1, map<int, int>());
		cur.assign(n + q + 2, multiset<pii>());
		ans.assign(q + 1, {0, 0});
		stores.assign(n + k + 1, {0, 0});
		qq.clear(), v.clear();
		seg::init_();	
	}
	void add_store(int id, int l, int tp, int a, int b) {
		stores[id] = {l, tp};
		v.push_back(l);
		qq.push_back({a, 1, id});
		qq.push_back({b + 1, 2, id});
	}
	void add_query(int id, int l, int y) {
		ans[id].first = l;
		v.push_back(l);
		qq.push_back({y, 3, id});
	}
	void update(int x) {
		auto it = cur[x].begin();
		if(it == cur[x].end()) seg::change(v[x], INF);
		else seg::change(v[x], v[it -> first]);
	}
	void add(int id) {
		int tp = stores[id].second, l = stores[id].first;
		s[tp][l] ++;
		if(s[tp][l] > 1) return; 
		int pre, nxt = 0;
		auto it1 = s[tp].upper_bound(l);
		auto it2 = s[tp].lower_bound(l);
		if(it2 == s[tp].begin()) pre = 0;
		else pre = prev(it2) -> first;
		if(it1 != s[tp].end()) {
			nxt = it1 -> first;
			cur[nxt].erase(cur[nxt].find({pre, tp}));
			cur[nxt].insert({l, tp});
			update(nxt);
		} 
		cur[l].insert({pre, tp});
		update(l);
	}
	int query(int x) {
		return seg::answer(x);
	}

/*	int query(int x) {
		int L = -1, R = 1e8;
		while(R - L > 1) {
			int mid = (L + R) / 2;
			int val = seg::ask(x + mid + 1);
			if(val < x - mid) L = mid;
			else R = mid;
		}
		if(R == 1e8) return -1;
		else return R;
	}
*/	void remove(int id) {
		int tp = stores[id].second, l = stores[id].first;
		s[tp][l] --;
		if(s[tp][l] > 0) return;
		int pre, nxt;
		s[tp].erase(s[tp].find(l));
		auto it1 = s[tp].upper_bound(l);
		auto it2 = s[tp].lower_bound(l);
		if(it2 == s[tp].begin()) pre = 0;
		else pre = prev(it2) -> first;
		if(it1 != s[tp].end()) {
			nxt = it1 -> first;
			cur[nxt].erase(cur[nxt].find({l, tp}));
			cur[nxt].insert({pre, tp});
			update(nxt);
		} 
		cur[l].erase({pre, tp});
		update(l);
	}
	void solve() {
		rep(i, 1, k) add_store(n + i, INF, i, -INF, INF);
		v.push_back(-INF);
		sort(all(v)), v.resize(unique(all(v)) - v.begin());
		rep(i, 1, n + k) stores[i].first = lower_bound(all(v), stores[i].first) - v.begin();
		rep(i, 1, q) ans[i].first = lower_bound(all(v), ans[i].first) - v.begin();
		sort(all(qq));
		for(auto i : qq) {
			if(i.tp == 1) add(i.id); 
			else if(i.tp == 2) remove(i.id);
			else ans[i.id].second = query(v[ans[i.id].first]);
		}
		rep(i, 1, q) cout << ans[i].second << "\n";
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k, q; cin >> n >> k >> q;
	init_(n, k, q);
	rep(i ,1, n) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		add_store(i, x, t, a, b);
	}
	rep(i, 1, q) {
		int l, y; cin >> l >> y;
		add_query(i, l, y);
	}
	solve();
	return 0;

}

Compilation message

new_home.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
new_home.cpp: In function 'int seg::get_lb(int, int, int, int, int)':
new_home.cpp:48:7: warning: unused variable 'mid' [-Wunused-variable]
   48 |   int mid = (L + R) / 2;
      |       ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 587464 KB Output is correct
2 Correct 299 ms 587368 KB Output is correct
3 Correct 298 ms 587464 KB Output is correct
4 Incorrect 297 ms 587380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 587464 KB Output is correct
2 Correct 299 ms 587368 KB Output is correct
3 Correct 298 ms 587464 KB Output is correct
4 Incorrect 297 ms 587380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2934 ms 677000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3167 ms 666764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 587464 KB Output is correct
2 Correct 299 ms 587368 KB Output is correct
3 Correct 298 ms 587464 KB Output is correct
4 Incorrect 297 ms 587380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 587464 KB Output is correct
2 Correct 299 ms 587368 KB Output is correct
3 Correct 298 ms 587464 KB Output is correct
4 Incorrect 297 ms 587380 KB Output isn't correct
5 Halted 0 ms 0 KB -