oj.uz

Submission #566027

# Submission time Handle Problem Language Result Execution time Memory
566027 2022-05-21T16:57:54 Z ngpin04 New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 531756 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 6e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct event {
	int y,id,t;
	event(int _y = 0, int _id = 0, int _t = 0) {
		y = _y;
		id = _id;
		t = _t;
	}

	bool operator < (const event &e) const {
		return y < e.y || (y == e.y && t < e.t);	
	}
};

multiset <int> st[2][N << 2];
multiset <int> pos[N];

vector <event> events;
vector <int> pos_x;

int ans[N];
int _x[N];	
int t[N];
int n,k,q,sz,cnt;

int getind(int x) {
	return upper_bound(ALL(pos_x), x) - pos_x.begin();
}

void update(int id, int l, int r, int u, int v, int val, int t) {
	if (l > v || r < u)
		return;
	if (l >= u && r <= v) {
		if (t > 0)
			st[t - 1][id].insert(val);
		else
			st[(-t) - 1][id].erase(st[(-t) - 1][id].find(val));
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, u, v, val, t);
	update(id << 1 | 1, mid + 1, r, u, v, val, t);
}

void update(int l, int r, int val, int t) {
	// cerr << "update " << l << " " << r << " " << val << " " << t << "\n";
	update(1, 1, sz, l, r, val, t);
}

pair <int, int> getans(int id, int l, int r, int pos) {
	if (l > pos || r < pos)
		return mp(oo, -oo);

	int mx = -oo, mn = oo;
	if (st[0][id].size())
		mn = *st[0][id].begin();
	if (st[1][id].size())
		mx = *prev(st[1][id].end());

	if (l == r)
		return mp(mn, mx);
	int mid = (l + r) >> 1;
	pair <int, int> pir;

	pir = getans(id << 1, l, mid, pos);
	mini(mn, pir.fi);
	maxi(mx, pir.se);

	pir = getans(id << 1 | 1, mid + 1, r, pos);
	mini(mn, pir.fi);
	maxi(mx, pir.se);
	return mp(mn, mx);
}

int getans(int x) {
	int pos = getind(x);
	pair <int, int> pir = getans(1, 1, sz, pos);
	int minl = pir.fi;
	int maxr = pir.se;
	if (minl == oo && maxr == -oo)
		return -1;
	int res = 0;
	maxi(res, pos_x[pos - 1] - minl);
	maxi(res, maxr - pos_x[pos - 1]);
	return res;
}

void add(int l, int r, int t) {
	int mid = (l + r) >> 1;
	int pl = getind(l);
	int pr = getind(r);
	int pmid = getind(mid);
	update(pl, pmid, l, t * 1);
	if (pmid < pr)
		update(pmid + 1, pr, r, t * 2);
}

void solve(vector <pair <int, int>> events) {
	for (pair <int, int> pir : events) {
		// cerr << cnt << "\n";
		int x = _x[pir.fi];
		int c = t[pir.fi];
		int p = getind(x);

		// cerr << pir.fi << " " << pir.se << " " << x << " " << c << "\n";

		if (pir.se == 2) {
			ans[pir.fi - n] = (cnt < k) ? -1 : getans(x);
			// cerr << "ans = " << ans[pir.fi - n] << "\n";
		} else if (pir.se == 0) {
			if (!pos[c].size()) {
				cnt++;			
				update(1, p, x, 2);
				update(p, sz, x, 1);
				pos[c].insert(x);
				continue;
			}

			auto it = pos[c].lower_bound(x);
			if (it == pos[c].begin()) {
				int tmp = getind(*it);
				update(1, tmp, *it, -2);
				update(1, p, x, 2);
				add(x, *it, 1);
				pos[c].insert(x);
				continue;
			} 

			if (it == pos[c].end()) {
				it--;
				int tmp = getind(*it);
				update(tmp, sz, *it, -1);
				update(p, sz, x, 1);
				add(*it, x, 1);
				pos[c].insert(x);
				continue;
			}

			int l = *prev(it);
			int r = *it;
			add(l, r, -1);
			add(l, x, 1);
			add(x, r, 1);
			
			pos[c].insert(x);
		} else {
			pos[c].erase(pos[c].find(x));

			if (!pos[c].size()) {
				update(1, p, x, -2);
				update(p, sz, x, -1);
				cnt--;
				continue;
			}

			auto it = pos[c].lower_bound(x);
			if (it == pos[c].begin()) {
				int tmp = getind(*it);
				update(1, tmp, *it, 2);
				update(1, p, x, -2);
				add(x, *it, -1);
				continue;
			} 

			if (it == pos[c].end()) {
				it--;	
				int tmp = getind(*it);
				update(tmp, sz, *it, 1);
				update(p, sz, x, -1);
				add(*it, x, -1);
				continue;
			}

			int l = *prev(it);
			int r = *it;
			add(l, r, 1);
			add(l, x, -1);
			add(x, r, -1);
		}
	}
}	

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) {
		int a,b;
		cin >> _x[i] >> t[i] >> a >> b;
		events.push_back(event(a, i, 0));
		events.push_back(event(b + 1, i, 1));
		pos_x.push_back(_x[i]);
	}

	for (int i = 1; i <= q; i++) {
		int y; 
		cin >> _x[n + i] >> y;
		events.push_back(event(y, n + i, 2));
		pos_x.push_back(_x[n + i]);
	}
	sort(ALL(pos_x));
	sz = n + q;

	sort(ALL(events));
	for (int l = 0; l < (int) events.size();) {
		int r = l;
		while (r < (int) events.size() && events[l].y == events[r].y)
			r++;

		vector <pair <int, int>> pir;
		for (int i = l; i < r; i++)
			pir.push_back(mp(events[i].id, events[i].t));

		solve(pir);
		l = r;
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 253948 KB Output is correct
2 Correct 118 ms 253836 KB Output is correct
3 Correct 125 ms 253864 KB Output is correct
4 Correct 123 ms 253860 KB Output is correct
5 Correct 125 ms 253996 KB Output is correct
6 Correct 132 ms 254068 KB Output is correct
7 Correct 120 ms 254056 KB Output is correct
8 Correct 124 ms 254124 KB Output is correct
9 Correct 123 ms 254116 KB Output is correct
10 Correct 124 ms 254176 KB Output is correct
11 Correct 120 ms 254004 KB Output is correct
12 Correct 121 ms 253900 KB Output is correct
13 Correct 122 ms 254028 KB Output is correct
14 Correct 125 ms 253988 KB Output is correct
15 Correct 119 ms 254028 KB Output is correct
16 Correct 122 ms 253996 KB Output is correct
17 Correct 124 ms 254088 KB Output is correct
18 Correct 119 ms 254080 KB Output is correct
19 Correct 122 ms 254212 KB Output is correct
20 Correct 119 ms 254048 KB Output is correct
21 Correct 118 ms 254028 KB Output is correct
22 Correct 124 ms 254156 KB Output is correct
23 Correct 122 ms 254108 KB Output is correct
24 Correct 130 ms 254156 KB Output is correct
25 Correct 121 ms 254056 KB Output is correct
26 Correct 122 ms 253944 KB Output is correct
27 Correct 125 ms 254000 KB Output is correct
28 Correct 124 ms 253968 KB Output is correct
29 Correct 121 ms 254004 KB Output is correct
30 Correct 119 ms 253888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 253948 KB Output is correct
2 Correct 118 ms 253836 KB Output is correct
3 Correct 125 ms 253864 KB Output is correct
4 Correct 123 ms 253860 KB Output is correct
5 Correct 125 ms 253996 KB Output is correct
6 Correct 132 ms 254068 KB Output is correct
7 Correct 120 ms 254056 KB Output is correct
8 Correct 124 ms 254124 KB Output is correct
9 Correct 123 ms 254116 KB Output is correct
10 Correct 124 ms 254176 KB Output is correct
11 Correct 120 ms 254004 KB Output is correct
12 Correct 121 ms 253900 KB Output is correct
13 Correct 122 ms 254028 KB Output is correct
14 Correct 125 ms 253988 KB Output is correct
15 Correct 119 ms 254028 KB Output is correct
16 Correct 122 ms 253996 KB Output is correct
17 Correct 124 ms 254088 KB Output is correct
18 Correct 119 ms 254080 KB Output is correct
19 Correct 122 ms 254212 KB Output is correct
20 Correct 119 ms 254048 KB Output is correct
21 Correct 118 ms 254028 KB Output is correct
22 Correct 124 ms 254156 KB Output is correct
23 Correct 122 ms 254108 KB Output is correct
24 Correct 130 ms 254156 KB Output is correct
25 Correct 121 ms 254056 KB Output is correct
26 Correct 122 ms 253944 KB Output is correct
27 Correct 125 ms 254000 KB Output is correct
28 Correct 124 ms 253968 KB Output is correct
29 Correct 121 ms 254004 KB Output is correct
30 Correct 119 ms 253888 KB Output is correct
31 Correct 2585 ms 307544 KB Output is correct
32 Correct 586 ms 261764 KB Output is correct
33 Correct 1166 ms 270452 KB Output is correct
34 Correct 2503 ms 280892 KB Output is correct
35 Correct 2133 ms 299008 KB Output is correct
36 Correct 1157 ms 281284 KB Output is correct
37 Correct 859 ms 263132 KB Output is correct
38 Correct 671 ms 262188 KB Output is correct
39 Correct 630 ms 261148 KB Output is correct
40 Correct 634 ms 261176 KB Output is correct
41 Correct 1157 ms 261500 KB Output is correct
42 Correct 1074 ms 261488 KB Output is correct
43 Correct 277 ms 266976 KB Output is correct
44 Correct 1044 ms 261448 KB Output is correct
45 Correct 805 ms 261412 KB Output is correct
46 Correct 666 ms 261444 KB Output is correct
47 Correct 429 ms 260928 KB Output is correct
48 Correct 433 ms 260884 KB Output is correct
49 Correct 549 ms 261132 KB Output is correct
50 Correct 710 ms 261228 KB Output is correct
51 Correct 541 ms 261072 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 531756 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 5058 ms 463100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 253948 KB Output is correct
2 Correct 118 ms 253836 KB Output is correct
3 Correct 125 ms 253864 KB Output is correct
4 Correct 123 ms 253860 KB Output is correct
5 Correct 125 ms 253996 KB Output is correct
6 Correct 132 ms 254068 KB Output is correct
7 Correct 120 ms 254056 KB Output is correct
8 Correct 124 ms 254124 KB Output is correct
9 Correct 123 ms 254116 KB Output is correct
10 Correct 124 ms 254176 KB Output is correct
11 Correct 120 ms 254004 KB Output is correct
12 Correct 121 ms 253900 KB Output is correct
13 Correct 122 ms 254028 KB Output is correct
14 Correct 125 ms 253988 KB Output is correct
15 Correct 119 ms 254028 KB Output is correct
16 Correct 122 ms 253996 KB Output is correct
17 Correct 124 ms 254088 KB Output is correct
18 Correct 119 ms 254080 KB Output is correct
19 Correct 122 ms 254212 KB Output is correct
20 Correct 119 ms 254048 KB Output is correct
21 Correct 118 ms 254028 KB Output is correct
22 Correct 124 ms 254156 KB Output is correct
23 Correct 122 ms 254108 KB Output is correct
24 Correct 130 ms 254156 KB Output is correct
25 Correct 121 ms 254056 KB Output is correct
26 Correct 122 ms 253944 KB Output is correct
27 Correct 125 ms 254000 KB Output is correct
28 Correct 124 ms 253968 KB Output is correct
29 Correct 121 ms 254004 KB Output is correct
30 Correct 119 ms 253888 KB Output is correct
31 Correct 2585 ms 307544 KB Output is correct
32 Correct 586 ms 261764 KB Output is correct
33 Correct 1166 ms 270452 KB Output is correct
34 Correct 2503 ms 280892 KB Output is correct
35 Correct 2133 ms 299008 KB Output is correct
36 Correct 1157 ms 281284 KB Output is correct
37 Correct 859 ms 263132 KB Output is correct
38 Correct 671 ms 262188 KB Output is correct
39 Correct 630 ms 261148 KB Output is correct
40 Correct 634 ms 261176 KB Output is correct
41 Correct 1157 ms 261500 KB Output is correct
42 Correct 1074 ms 261488 KB Output is correct
43 Correct 277 ms 266976 KB Output is correct
44 Correct 1044 ms 261448 KB Output is correct
45 Correct 805 ms 261412 KB Output is correct
46 Correct 666 ms 261444 KB Output is correct
47 Correct 429 ms 260928 KB Output is correct
48 Correct 433 ms 260884 KB Output is correct
49 Correct 549 ms 261132 KB Output is correct
50 Correct 710 ms 261228 KB Output is correct
51 Correct 541 ms 261072 KB Output is correct
52 Correct 831 ms 311172 KB Output is correct
53 Correct 811 ms 279468 KB Output is correct
54 Correct 2175 ms 326468 KB Output is correct
55 Correct 1014 ms 278328 KB Output is correct
56 Correct 963 ms 286640 KB Output is correct
57 Correct 1018 ms 266868 KB Output is correct
58 Correct 1199 ms 278460 KB Output is correct
59 Correct 1072 ms 286688 KB Output is correct
60 Correct 1131 ms 266768 KB Output is correct
61 Correct 245 ms 270324 KB Output is correct
62 Correct 838 ms 311476 KB Output is correct
63 Correct 1663 ms 311592 KB Output is correct
64 Correct 2007 ms 303328 KB Output is correct
65 Correct 2138 ms 275288 KB Output is correct
66 Correct 1064 ms 262364 KB Output is correct
67 Correct 2814 ms 275708 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 253948 KB Output is correct
2 Correct 118 ms 253836 KB Output is correct
3 Correct 125 ms 253864 KB Output is correct
4 Correct 123 ms 253860 KB Output is correct
5 Correct 125 ms 253996 KB Output is correct
6 Correct 132 ms 254068 KB Output is correct
7 Correct 120 ms 254056 KB Output is correct
8 Correct 124 ms 254124 KB Output is correct
9 Correct 123 ms 254116 KB Output is correct
10 Correct 124 ms 254176 KB Output is correct
11 Correct 120 ms 254004 KB Output is correct
12 Correct 121 ms 253900 KB Output is correct
13 Correct 122 ms 254028 KB Output is correct
14 Correct 125 ms 253988 KB Output is correct
15 Correct 119 ms 254028 KB Output is correct
16 Correct 122 ms 253996 KB Output is correct
17 Correct 124 ms 254088 KB Output is correct
18 Correct 119 ms 254080 KB Output is correct
19 Correct 122 ms 254212 KB Output is correct
20 Correct 119 ms 254048 KB Output is correct
21 Correct 118 ms 254028 KB Output is correct
22 Correct 124 ms 254156 KB Output is correct
23 Correct 122 ms 254108 KB Output is correct
24 Correct 130 ms 254156 KB Output is correct
25 Correct 121 ms 254056 KB Output is correct
26 Correct 122 ms 253944 KB Output is correct
27 Correct 125 ms 254000 KB Output is correct
28 Correct 124 ms 253968 KB Output is correct
29 Correct 121 ms 254004 KB Output is correct
30 Correct 119 ms 253888 KB Output is correct
31 Correct 2585 ms 307544 KB Output is correct
32 Correct 586 ms 261764 KB Output is correct
33 Correct 1166 ms 270452 KB Output is correct
34 Correct 2503 ms 280892 KB Output is correct
35 Correct 2133 ms 299008 KB Output is correct
36 Correct 1157 ms 281284 KB Output is correct
37 Correct 859 ms 263132 KB Output is correct
38 Correct 671 ms 262188 KB Output is correct
39 Correct 630 ms 261148 KB Output is correct
40 Correct 634 ms 261176 KB Output is correct
41 Correct 1157 ms 261500 KB Output is correct
42 Correct 1074 ms 261488 KB Output is correct
43 Correct 277 ms 266976 KB Output is correct
44 Correct 1044 ms 261448 KB Output is correct
45 Correct 805 ms 261412 KB Output is correct
46 Correct 666 ms 261444 KB Output is correct
47 Correct 429 ms 260928 KB Output is correct
48 Correct 433 ms 260884 KB Output is correct
49 Correct 549 ms 261132 KB Output is correct
50 Correct 710 ms 261228 KB Output is correct
51 Correct 541 ms 261072 KB Output is correct
52 Execution timed out 5036 ms 531756 KB Time limit exceeded
53 Halted 0 ms 0 KB -