oj.uz

Submission #543847

# Submission time Handle Problem Language Result Execution time Memory
543847 2022-03-31T13:47:31 Z amunduzbaev New Home (APIO18_new_home) C++17
15 / 100
 5000 ms 1048576 KB 
#include "bits/stdc++.h"
using namespace std;

namespace NLOGsq{

#define ar array
#define pq priority_queue

const int N = 3e5 + 5;
const int M = N * 20;
const int MX = 1e8 + 5;
 
struct ST{
	pq<int> tree[M][2], bad[M][2];
	int f[M][2], last;
	ST(){
		last = 0;
	}
	
	void make(int x){
		if(!f[x][0]) f[x][0] = ++last;
		if(!f[x][1]) f[x][1] = ++last;
		//~ assert(last < M);
	}
	
	void add(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1){
				tree[x][0].push(s + (lx - l));
			} else {
				tree[x][1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		make(x);
		add(l, r, s, t, lx, m, f[x][0]), add(l, r, s, t, m+1, rx, f[x][1]);
	}
	
	void bal(pq<int>& a, pq<int>& b){
		while(!a.empty() && !b.empty() && a.top() == b.top()){
			a.pop();
			b.pop();
		}
	}
	
	void del(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1){
				bad[x][0].push(s + (lx - l));
			} else {
				bad[x][1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		make(x);
		del(l, r, s, t, lx, m, f[x][0]), del(l, r, s, t, m+1, rx, f[x][1]);
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = 0;
		bal(tree[x][0], bad[x][0]);
		bal(tree[x][1], bad[x][1]);
		if(!tree[x][0].empty()) res = max(res, tree[x][0].top() + (i - lx));
		if(!tree[x][1].empty()) res = max(res, tree[x][1].top() - (i - lx));
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		if(i <= m) return max((f[x][0] ? get(i, lx, m, f[x][0]) : 0), res);
		else return max((f[x][1] ? get(i, m+1, rx, f[x][1]) : 0), res);
	}
}tree;
 
/*

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

*/

int x[N], t[N], a[N], b[N], l[N], y[N];
multiset<int> ss[N];

void solve(int n, int k, int q){ // assert(false);
	for(int i=0;i<n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		--t[i];
	}

	auto add = [&](int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		tree.add(l, m, 0, 1);
		tree.add(m + 1, r, r - m - 1, -1);
	}; auto inc = [&](int x) { tree.add(x, MX, 0, 1); };
	auto dec = [&](int x) { tree.add(0, x, x, -1); };
	
	auto dadd = [&](int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		tree.del(l, m, 0, 1);
		tree.del(m + 1, r, r - m - 1, -1);
	}; auto dinc = [&](int x) { tree.del(x, MX, 0, 1); };
	auto ddec = [&](int x) { tree.del(0, x, x, -1); };
	
	//~ bool is = 1;
	//~ for(int i=0;i<k;i++){
		//~ if(stor[i].empty()) { is = 0; break; }
		//~ sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
			//~ return (x[i] < x[j]);
		//~ });
		//~ for(int j=1;j<(int)stor[i].size();j++){
			//~ add(x[stor[i][j-1]], x[stor[i][j]]);
		//~ }
		
		//~ dec(x[stor[i][0]]);
		//~ inc(x[stor[i].back()]);
	//~ }
	
	vector<int> in(n); iota(in.begin(), in.end(), 0);
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	sort(in.begin(), in.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	sort(out.begin(), out.end(), [&](int i, int j){
		return (b[i] < b[j]);
	});
	vector<int> p(q);
	
	for(int i=0;i<q;i++){ p[i] = i;
		cin>>l[i]>>y[i];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (y[i] < y[j]);
	});
	
	int I = 0, O = 0, c = k;
	auto NEW = [&](int i){
		auto it = ss[t[i]].upper_bound(x[i]);
		if(ss[t[i]].empty()) c--;
		if(it == ss[t[i]].end()){
			if(it != ss[t[i]].begin()){
				it--;
				dinc(*it);
				add(*it, x[i]);
				inc(x[i]);
			} else {
				inc(x[i]);
				dec(x[i]);
			}
		} else {
			if(it == ss[t[i]].begin()){
				ddec(*it);
				add(x[i], *it);
				dec(x[i]);
			} else {
				auto R = it; it--;
				dadd(*it, *R);
				add(*it, x[i]);
				add(x[i], *R);
			}
		}
		
		ss[t[i]].insert(x[i]);
	};
	
	auto DEL = [&](int i){
		ss[t[i]].erase(ss[t[i]].find(x[i]));
		if(ss[t[i]].empty()) c++;
		auto it = ss[t[i]].upper_bound(x[i]);
		if(it == ss[t[i]].end()){
			if(it == ss[t[i]].begin()){
				dinc(x[i]);
				ddec(x[i]);
			} else {
				it--;
				dadd(*it, x[i]);
				dinc(x[i]);
				inc(*it);
			}
		} else {
			if(it == ss[t[i]].begin()){
				dadd(x[i], *it);
				ddec(x[i]);
				dec(*it);
			} else {
				auto R = it; it--;
				dadd(*it, x[i]);
				dadd(x[i], *R);
				add(*it, *R);
			}
		}
	};
	
	vector<int> res(q);
	for(auto i : p){
		while(I < n && a[in[I]] <= y[i]){
			NEW(in[I]);
			I++;
		}
		
		while(O < n && b[out[O]] < y[i]){
			DEL(out[O]);
			O++;
		}
		
		if(!c) res[i] = tree.get(l[i]);
		else res[i] = -1;
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
};

namespace temp{

const int N = 3e5 + 5;
const int M = N * 30;
const int MX = 1e8 + 5;

struct ST{
	int tree[M][2], f[M][2];
	int last;
	
	ST(){
		memset(tree, -1, sizeof tree);
		last = 0;
	}
	
	void make(int x){
		if(!f[x][0]) f[x][0] = ++last;
		if(!f[x][1]) f[x][1] = ++last;
	}
	
	void umax(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if(t == 1) tree[x][0] = max(tree[x][0], s + (lx - l));
			else tree[x][1] = max(tree[x][1], s - (lx - l));
			return;
		} int m = (lx + rx) >> 1;
		make(x);
		umax(l, r, s, t, lx, m, f[x][0]);
		umax(l, r, s, t, m+1, rx, f[x][1]);
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = 0;
		if(~tree[x][0]) res = max(res, tree[x][0] + (i - lx));
		if(~tree[x][1]) res = max(res, tree[x][1] - (i - lx));
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		if(i <= m) return max((f[x][0] ? get(i, lx, m, f[x][0]) : 0), res);
		else return max((f[x][1] ? get(i, m+1, rx, f[x][1]) : 0), res);
	}
}tree;

int x[N], t[N], a[N], b[N], l[N], y[N];
multiset<int> ss[N];
vector<int> stor[N];

void solve(int n, int k, int q){
	for(int i=0;i<n;i++){
		cin>>x[i]>>t[i]>>a[i]>>b[i];
		--t[i];
		stor[t[i]].push_back(i);
	}

	auto add = [&](int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		tree.umax(l, m, 0, 1);
		tree.umax(m + 1, r, r - m - 1, -1);
	}; auto inc = [&](int x) { tree.umax(x, MX, 0, 1); };
	auto dec = [&](int x) { tree.umax(0, x, x, -1); };
	
	vector<int> out(n); iota(out.begin(), out.end(), 0);
	sort(out.begin(), out.end(), [&](int i, int j){
		return (b[i] < b[j]);
	});
	vector<int> p(q);
	
	for(int i=0;i<q;i++){ p[i] = i;
		cin>>l[i]>>y[i];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (y[i] < y[j]);
	});
	
	int O = 0, c = 0;
	
	for(int i=0;i<k;i++){
		if(stor[i].empty()) { c++; break; }
		sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
			return (x[i] < x[j]);
		});
		
		for(int j=1;j<(int)stor[i].size();j++){
			add(x[stor[i][j-1]], x[stor[i][j]]);
		}
		
		inc(x[stor[i].back()]);
		dec(x[stor[i][0]]);
	}
	
	auto DEL = [&](int i){
		ss[t[i]].erase(ss[t[i]].find(x[i]));
		if(ss[t[i]].empty()) c++;
		auto it = ss[t[i]].upper_bound(x[i]);
		if(it == ss[t[i]].end()){
			if(it != ss[t[i]].begin()){
				it--;
				inc(*it);
			}
		} else {
			if(it == ss[t[i]].begin()){
				dec(*it);
			} else {
				auto R = it; it--;
				add(*it, *R);
			}
		}
	};
	
	vector<int> res(q);
	for(auto i : p){
		while(O < n && b[out[O]] < y[i]){
			DEL(out[O]);
			O++;
		}
		
		if(!c) res[i] = tree.get(l[i]);
		else res[i] = -1;
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	if(n <= 60000 && q <= 60000){
		NLOGsq::solve(n, k, q);
	} else {
		temp::solve(n, k, q);
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 857624 KB Output is correct
2 Correct 374 ms 857552 KB Output is correct
3 Correct 379 ms 857516 KB Output is correct
4 Correct 363 ms 857548 KB Output is correct
5 Correct 364 ms 857580 KB Output is correct
6 Correct 365 ms 859296 KB Output is correct
7 Correct 360 ms 858128 KB Output is correct
8 Correct 375 ms 858696 KB Output is correct
9 Correct 378 ms 858208 KB Output is correct
10 Correct 374 ms 859412 KB Output is correct
11 Correct 361 ms 858600 KB Output is correct
12 Correct 365 ms 859300 KB Output is correct
13 Correct 366 ms 858444 KB Output is correct
14 Correct 358 ms 858532 KB Output is correct
15 Correct 359 ms 858676 KB Output is correct
16 Correct 356 ms 858444 KB Output is correct
17 Correct 393 ms 858828 KB Output is correct
18 Correct 467 ms 858576 KB Output is correct
19 Correct 383 ms 858580 KB Output is correct
20 Correct 361 ms 858772 KB Output is correct
21 Correct 391 ms 857520 KB Output is correct
22 Correct 366 ms 858060 KB Output is correct
23 Correct 380 ms 858444 KB Output is correct
24 Correct 360 ms 858528 KB Output is correct
25 Correct 375 ms 858844 KB Output is correct
26 Correct 384 ms 858956 KB Output is correct
27 Correct 354 ms 857664 KB Output is correct
28 Correct 361 ms 858600 KB Output is correct
29 Correct 360 ms 858560 KB Output is correct
30 Correct 360 ms 858324 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 857624 KB Output is correct
2 Correct 374 ms 857552 KB Output is correct
3 Correct 379 ms 857516 KB Output is correct
4 Correct 363 ms 857548 KB Output is correct
5 Correct 364 ms 857580 KB Output is correct
6 Correct 365 ms 859296 KB Output is correct
7 Correct 360 ms 858128 KB Output is correct
8 Correct 375 ms 858696 KB Output is correct
9 Correct 378 ms 858208 KB Output is correct
10 Correct 374 ms 859412 KB Output is correct
11 Correct 361 ms 858600 KB Output is correct
12 Correct 365 ms 859300 KB Output is correct
13 Correct 366 ms 858444 KB Output is correct
14 Correct 358 ms 858532 KB Output is correct
15 Correct 359 ms 858676 KB Output is correct
16 Correct 356 ms 858444 KB Output is correct
17 Correct 393 ms 858828 KB Output is correct
18 Correct 467 ms 858576 KB Output is correct
19 Correct 383 ms 858580 KB Output is correct
20 Correct 361 ms 858772 KB Output is correct
21 Correct 391 ms 857520 KB Output is correct
22 Correct 366 ms 858060 KB Output is correct
23 Correct 380 ms 858444 KB Output is correct
24 Correct 360 ms 858528 KB Output is correct
25 Correct 375 ms 858844 KB Output is correct
26 Correct 384 ms 858956 KB Output is correct
27 Correct 354 ms 857664 KB Output is correct
28 Correct 361 ms 858600 KB Output is correct
29 Correct 360 ms 858560 KB Output is correct
30 Correct 360 ms 858324 KB Output is correct
31 Runtime error 2598 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1344 ms 935332 KB Output is correct
2 Correct 1083 ms 937712 KB Output is correct
3 Correct 1160 ms 920340 KB Output is correct
4 Correct 1341 ms 932380 KB Output is correct
5 Correct 969 ms 937200 KB Output is correct
6 Correct 1045 ms 937744 KB Output is correct
7 Correct 1049 ms 920396 KB Output is correct
8 Correct 1297 ms 932184 KB Output is correct
9 Correct 1347 ms 937176 KB Output is correct
10 Correct 1230 ms 938828 KB Output is correct
11 Correct 987 ms 936644 KB Output is correct
12 Correct 1101 ms 938236 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5071 ms 936016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 857624 KB Output is correct
2 Correct 374 ms 857552 KB Output is correct
3 Correct 379 ms 857516 KB Output is correct
4 Correct 363 ms 857548 KB Output is correct
5 Correct 364 ms 857580 KB Output is correct
6 Correct 365 ms 859296 KB Output is correct
7 Correct 360 ms 858128 KB Output is correct
8 Correct 375 ms 858696 KB Output is correct
9 Correct 378 ms 858208 KB Output is correct
10 Correct 374 ms 859412 KB Output is correct
11 Correct 361 ms 858600 KB Output is correct
12 Correct 365 ms 859300 KB Output is correct
13 Correct 366 ms 858444 KB Output is correct
14 Correct 358 ms 858532 KB Output is correct
15 Correct 359 ms 858676 KB Output is correct
16 Correct 356 ms 858444 KB Output is correct
17 Correct 393 ms 858828 KB Output is correct
18 Correct 467 ms 858576 KB Output is correct
19 Correct 383 ms 858580 KB Output is correct
20 Correct 361 ms 858772 KB Output is correct
21 Correct 391 ms 857520 KB Output is correct
22 Correct 366 ms 858060 KB Output is correct
23 Correct 380 ms 858444 KB Output is correct
24 Correct 360 ms 858528 KB Output is correct
25 Correct 375 ms 858844 KB Output is correct
26 Correct 384 ms 858956 KB Output is correct
27 Correct 354 ms 857664 KB Output is correct
28 Correct 361 ms 858600 KB Output is correct
29 Correct 360 ms 858560 KB Output is correct
30 Correct 360 ms 858324 KB Output is correct
31 Runtime error 2598 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 857624 KB Output is correct
2 Correct 374 ms 857552 KB Output is correct
3 Correct 379 ms 857516 KB Output is correct
4 Correct 363 ms 857548 KB Output is correct
5 Correct 364 ms 857580 KB Output is correct
6 Correct 365 ms 859296 KB Output is correct
7 Correct 360 ms 858128 KB Output is correct
8 Correct 375 ms 858696 KB Output is correct
9 Correct 378 ms 858208 KB Output is correct
10 Correct 374 ms 859412 KB Output is correct
11 Correct 361 ms 858600 KB Output is correct
12 Correct 365 ms 859300 KB Output is correct
13 Correct 366 ms 858444 KB Output is correct
14 Correct 358 ms 858532 KB Output is correct
15 Correct 359 ms 858676 KB Output is correct
16 Correct 356 ms 858444 KB Output is correct
17 Correct 393 ms 858828 KB Output is correct
18 Correct 467 ms 858576 KB Output is correct
19 Correct 383 ms 858580 KB Output is correct
20 Correct 361 ms 858772 KB Output is correct
21 Correct 391 ms 857520 KB Output is correct
22 Correct 366 ms 858060 KB Output is correct
23 Correct 380 ms 858444 KB Output is correct
24 Correct 360 ms 858528 KB Output is correct
25 Correct 375 ms 858844 KB Output is correct
26 Correct 384 ms 858956 KB Output is correct
27 Correct 354 ms 857664 KB Output is correct
28 Correct 361 ms 858600 KB Output is correct
29 Correct 360 ms 858560 KB Output is correct
30 Correct 360 ms 858324 KB Output is correct
31 Runtime error 2598 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -