oj.uz

Submission #414365

# Submission time Handle Problem Language Result Execution time Memory
414365 2021-05-30T11:35:31 Z hhhhaura New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 672504 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(!nd) return abs(x - max(L, x));
		else if(L == R) {
			int l = 2 * x - L;
			if(L == INF) return -1;
			else return L - x;
		}
		else {
			int mid = (L + R) / 2, l = 2 * x - mid - 1;
			if(min(cur, seg[rch[nd]]) < l || mid <= x) 
				return get_lb(rch[nd], mid + 1, R, x, cur);
			else return get_lb(lch[nd], L, mid, x, min(cur, seg[rch[nd]]));
		}
	}
*/
	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)
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 587312 KB Output is correct
2 Correct 301 ms 587460 KB Output is correct
3 Correct 292 ms 587368 KB Output is correct
4 Correct 294 ms 587364 KB Output is correct
5 Correct 304 ms 587420 KB Output is correct
6 Correct 721 ms 587508 KB Output is correct
7 Correct 1052 ms 587568 KB Output is correct
8 Correct 1356 ms 587572 KB Output is correct
9 Correct 1383 ms 587608 KB Output is correct
10 Correct 980 ms 587532 KB Output is correct
11 Correct 1100 ms 587512 KB Output is correct
12 Correct 956 ms 587504 KB Output is correct
13 Correct 1166 ms 587504 KB Output is correct
14 Correct 987 ms 587516 KB Output is correct
15 Correct 1222 ms 587532 KB Output is correct
16 Correct 1368 ms 587544 KB Output is correct
17 Correct 1067 ms 587576 KB Output is correct
18 Correct 1243 ms 587536 KB Output is correct
19 Correct 1334 ms 587596 KB Output is correct
20 Correct 1146 ms 587512 KB Output is correct
21 Correct 298 ms 587500 KB Output is correct
22 Correct 1569 ms 587620 KB Output is correct
23 Correct 1358 ms 587560 KB Output is correct
24 Correct 1299 ms 587564 KB Output is correct
25 Correct 1128 ms 587516 KB Output is correct
26 Correct 906 ms 587520 KB Output is correct
27 Correct 308 ms 587500 KB Output is correct
28 Correct 964 ms 587508 KB Output is correct
29 Correct 1027 ms 587532 KB Output is correct
30 Correct 863 ms 587492 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 587312 KB Output is correct
2 Correct 301 ms 587460 KB Output is correct
3 Correct 292 ms 587368 KB Output is correct
4 Correct 294 ms 587364 KB Output is correct
5 Correct 304 ms 587420 KB Output is correct
6 Correct 721 ms 587508 KB Output is correct
7 Correct 1052 ms 587568 KB Output is correct
8 Correct 1356 ms 587572 KB Output is correct
9 Correct 1383 ms 587608 KB Output is correct
10 Correct 980 ms 587532 KB Output is correct
11 Correct 1100 ms 587512 KB Output is correct
12 Correct 956 ms 587504 KB Output is correct
13 Correct 1166 ms 587504 KB Output is correct
14 Correct 987 ms 587516 KB Output is correct
15 Correct 1222 ms 587532 KB Output is correct
16 Correct 1368 ms 587544 KB Output is correct
17 Correct 1067 ms 587576 KB Output is correct
18 Correct 1243 ms 587536 KB Output is correct
19 Correct 1334 ms 587596 KB Output is correct
20 Correct 1146 ms 587512 KB Output is correct
21 Correct 298 ms 587500 KB Output is correct
22 Correct 1569 ms 587620 KB Output is correct
23 Correct 1358 ms 587560 KB Output is correct
24 Correct 1299 ms 587564 KB Output is correct
25 Correct 1128 ms 587516 KB Output is correct
26 Correct 906 ms 587520 KB Output is correct
27 Correct 308 ms 587500 KB Output is correct
28 Correct 964 ms 587508 KB Output is correct
29 Correct 1027 ms 587532 KB Output is correct
30 Correct 863 ms 587492 KB Output is correct
31 Execution timed out 5064 ms 600096 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5101 ms 672504 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 5071 ms 662716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 587312 KB Output is correct
2 Correct 301 ms 587460 KB Output is correct
3 Correct 292 ms 587368 KB Output is correct
4 Correct 294 ms 587364 KB Output is correct
5 Correct 304 ms 587420 KB Output is correct
6 Correct 721 ms 587508 KB Output is correct
7 Correct 1052 ms 587568 KB Output is correct
8 Correct 1356 ms 587572 KB Output is correct
9 Correct 1383 ms 587608 KB Output is correct
10 Correct 980 ms 587532 KB Output is correct
11 Correct 1100 ms 587512 KB Output is correct
12 Correct 956 ms 587504 KB Output is correct
13 Correct 1166 ms 587504 KB Output is correct
14 Correct 987 ms 587516 KB Output is correct
15 Correct 1222 ms 587532 KB Output is correct
16 Correct 1368 ms 587544 KB Output is correct
17 Correct 1067 ms 587576 KB Output is correct
18 Correct 1243 ms 587536 KB Output is correct
19 Correct 1334 ms 587596 KB Output is correct
20 Correct 1146 ms 587512 KB Output is correct
21 Correct 298 ms 587500 KB Output is correct
22 Correct 1569 ms 587620 KB Output is correct
23 Correct 1358 ms 587560 KB Output is correct
24 Correct 1299 ms 587564 KB Output is correct
25 Correct 1128 ms 587516 KB Output is correct
26 Correct 906 ms 587520 KB Output is correct
27 Correct 308 ms 587500 KB Output is correct
28 Correct 964 ms 587508 KB Output is correct
29 Correct 1027 ms 587532 KB Output is correct
30 Correct 863 ms 587492 KB Output is correct
31 Execution timed out 5064 ms 600096 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 587312 KB Output is correct
2 Correct 301 ms 587460 KB Output is correct
3 Correct 292 ms 587368 KB Output is correct
4 Correct 294 ms 587364 KB Output is correct
5 Correct 304 ms 587420 KB Output is correct
6 Correct 721 ms 587508 KB Output is correct
7 Correct 1052 ms 587568 KB Output is correct
8 Correct 1356 ms 587572 KB Output is correct
9 Correct 1383 ms 587608 KB Output is correct
10 Correct 980 ms 587532 KB Output is correct
11 Correct 1100 ms 587512 KB Output is correct
12 Correct 956 ms 587504 KB Output is correct
13 Correct 1166 ms 587504 KB Output is correct
14 Correct 987 ms 587516 KB Output is correct
15 Correct 1222 ms 587532 KB Output is correct
16 Correct 1368 ms 587544 KB Output is correct
17 Correct 1067 ms 587576 KB Output is correct
18 Correct 1243 ms 587536 KB Output is correct
19 Correct 1334 ms 587596 KB Output is correct
20 Correct 1146 ms 587512 KB Output is correct
21 Correct 298 ms 587500 KB Output is correct
22 Correct 1569 ms 587620 KB Output is correct
23 Correct 1358 ms 587560 KB Output is correct
24 Correct 1299 ms 587564 KB Output is correct
25 Correct 1128 ms 587516 KB Output is correct
26 Correct 906 ms 587520 KB Output is correct
27 Correct 308 ms 587500 KB Output is correct
28 Correct 964 ms 587508 KB Output is correct
29 Correct 1027 ms 587532 KB Output is correct
30 Correct 863 ms 587492 KB Output is correct
31 Execution timed out 5064 ms 600096 KB Time limit exceeded
32 Halted 0 ms 0 KB -