oj.uz

Submission #543853

# Submission time Handle Problem Language Result Execution time Memory
543853 2022-03-31T13:51:51 Z amunduzbaev New Home (APIO18_new_home) C++17
57 / 100
 3375 ms 766332 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 * 30;
const int MX = 1e8 + 5;
 
struct node{
	pq<int> in[2], del[2];
	int f[2];
	
	node (){
		f[0] = f[1] = 0;
	}
};
 
node def;
 
struct ST{
	vector<node> tree;
	int last;
	ST(){
		tree.push_back(def);
		last = 0;
	}
	
	void make_l(int x){
		//~ tree.push_back(def);
		if(tree[x].f[0]) return;
		tree.push_back(def);
		tree[x].f[0] = ++last; // tree[x].f[1] = ++last;
		//~ assert(last < M);
	}
	void make_r(int x){
		//~ tree.push_back(def);
		if(tree[x].f[1]) return;
		tree.push_back(def);
		tree[x].f[1] = ++last; // tree[x].f[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].in[0].push(s + (lx - l));
			} else {
				tree[x].in[1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		//~ make(x);
		if(lx <= r && m >= l){
			make_l(x);
			add(l, r, s, t, lx, m, tree[x].f[0]);
		} if(m + 1 <= r && rx >= l){
			make_r(x);
			add(l, r, s, t, m+1, rx, tree[x].f[1]);
		}
		//~ add(l, r, s, t, lx, m, tree[x].f[0]), add(l, r, s, t, m+1, rx, tree[x].f[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){
				tree[x].del[0].push(s + (lx - l));
			} else {
				tree[x].del[1].push(s - (lx - l));
			} return;
		} int m = (lx + rx) >> 1;
		if(lx <= r && m >= l){
			make_l(x);
			del(l, r, s, t, lx, m, tree[x].f[0]);
		} if(m + 1 <= r && rx >= l){
			make_r(x);
			del(l, r, s, t, m+1, rx, tree[x].f[1]);
		}
	}
	
	int get(int i, int lx = 0, int rx = MX, int x = 0){
		int res = 0;
		bal(tree[x].in[0], tree[x].del[0]);
		bal(tree[x].in[1], tree[x].del[1]);
		if(!tree[x].in[0].empty()) res = max(res, tree[x].in[0].top() + (i - lx));
		if(!tree[x].in[1].empty()) res = max(res, tree[x].in[1].top() - (i - lx));
		if(lx == rx) return res;
		int m = (lx + rx) >> 1;
		if(i <= m) return max((tree[x].f[0] ? get(i, lx, m, tree[x].f[0]) : 0), res);
		else return max((tree[x].f[1] ? get(i, m+1, rx, tree[x].f[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);
		ss[t[i]].insert(x[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 42 ms 105928 KB Output is correct
2 Correct 41 ms 105952 KB Output is correct
3 Correct 42 ms 105932 KB Output is correct
4 Correct 44 ms 106412 KB Output is correct
5 Correct 44 ms 106024 KB Output is correct
6 Correct 56 ms 115904 KB Output is correct
7 Correct 45 ms 108380 KB Output is correct
8 Correct 50 ms 110776 KB Output is correct
9 Correct 49 ms 108376 KB Output is correct
10 Correct 59 ms 115648 KB Output is correct
11 Correct 51 ms 110992 KB Output is correct
12 Correct 56 ms 115960 KB Output is correct
13 Correct 48 ms 110980 KB Output is correct
14 Correct 50 ms 111000 KB Output is correct
15 Correct 49 ms 110916 KB Output is correct
16 Correct 48 ms 110864 KB Output is correct
17 Correct 50 ms 110908 KB Output is correct
18 Correct 50 ms 110844 KB Output is correct
19 Correct 51 ms 110916 KB Output is correct
20 Correct 55 ms 110944 KB Output is correct
21 Correct 44 ms 106044 KB Output is correct
22 Correct 45 ms 108380 KB Output is correct
23 Correct 51 ms 110724 KB Output is correct
24 Correct 49 ms 110824 KB Output is correct
25 Correct 56 ms 110920 KB Output is correct
26 Correct 51 ms 111296 KB Output is correct
27 Correct 44 ms 106216 KB Output is correct
28 Correct 49 ms 110932 KB Output is correct
29 Correct 54 ms 111032 KB Output is correct
30 Correct 48 ms 110920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 105928 KB Output is correct
2 Correct 41 ms 105952 KB Output is correct
3 Correct 42 ms 105932 KB Output is correct
4 Correct 44 ms 106412 KB Output is correct
5 Correct 44 ms 106024 KB Output is correct
6 Correct 56 ms 115904 KB Output is correct
7 Correct 45 ms 108380 KB Output is correct
8 Correct 50 ms 110776 KB Output is correct
9 Correct 49 ms 108376 KB Output is correct
10 Correct 59 ms 115648 KB Output is correct
11 Correct 51 ms 110992 KB Output is correct
12 Correct 56 ms 115960 KB Output is correct
13 Correct 48 ms 110980 KB Output is correct
14 Correct 50 ms 111000 KB Output is correct
15 Correct 49 ms 110916 KB Output is correct
16 Correct 48 ms 110864 KB Output is correct
17 Correct 50 ms 110908 KB Output is correct
18 Correct 50 ms 110844 KB Output is correct
19 Correct 51 ms 110916 KB Output is correct
20 Correct 55 ms 110944 KB Output is correct
21 Correct 44 ms 106044 KB Output is correct
22 Correct 45 ms 108380 KB Output is correct
23 Correct 51 ms 110724 KB Output is correct
24 Correct 49 ms 110824 KB Output is correct
25 Correct 56 ms 110920 KB Output is correct
26 Correct 51 ms 111296 KB Output is correct
27 Correct 44 ms 106216 KB Output is correct
28 Correct 49 ms 110932 KB Output is correct
29 Correct 54 ms 111032 KB Output is correct
30 Correct 48 ms 110920 KB Output is correct
31 Correct 3375 ms 758748 KB Output is correct
32 Correct 278 ms 111624 KB Output is correct
33 Correct 2801 ms 756000 KB Output is correct
34 Correct 3324 ms 754772 KB Output is correct
35 Correct 3227 ms 765676 KB Output is correct
36 Correct 2917 ms 760652 KB Output is correct
37 Correct 2517 ms 762028 KB Output is correct
38 Correct 2144 ms 757720 KB Output is correct
39 Correct 1558 ms 759860 KB Output is correct
40 Correct 1642 ms 758456 KB Output is correct
41 Correct 2187 ms 760100 KB Output is correct
42 Correct 2078 ms 763912 KB Output is correct
43 Correct 103 ms 112704 KB Output is correct
44 Correct 2087 ms 759804 KB Output is correct
45 Correct 1862 ms 757392 KB Output is correct
46 Correct 1727 ms 756712 KB Output is correct
47 Correct 1043 ms 759536 KB Output is correct
48 Correct 1070 ms 758792 KB Output is correct
49 Correct 1230 ms 761736 KB Output is correct
50 Correct 1307 ms 766332 KB Output is correct
51 Correct 1282 ms 760952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1153 ms 198356 KB Output is correct
2 Correct 917 ms 200096 KB Output is correct
3 Correct 924 ms 183116 KB Output is correct
4 Correct 1147 ms 195028 KB Output is correct
5 Correct 814 ms 199600 KB Output is correct
6 Correct 895 ms 200016 KB Output is correct
7 Correct 773 ms 183032 KB Output is correct
8 Correct 1016 ms 194616 KB Output is correct
9 Correct 1058 ms 199716 KB Output is correct
10 Correct 983 ms 201428 KB Output is correct
11 Correct 695 ms 198628 KB Output is correct
12 Correct 828 ms 200632 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1332 ms 411416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 105928 KB Output is correct
2 Correct 41 ms 105952 KB Output is correct
3 Correct 42 ms 105932 KB Output is correct
4 Correct 44 ms 106412 KB Output is correct
5 Correct 44 ms 106024 KB Output is correct
6 Correct 56 ms 115904 KB Output is correct
7 Correct 45 ms 108380 KB Output is correct
8 Correct 50 ms 110776 KB Output is correct
9 Correct 49 ms 108376 KB Output is correct
10 Correct 59 ms 115648 KB Output is correct
11 Correct 51 ms 110992 KB Output is correct
12 Correct 56 ms 115960 KB Output is correct
13 Correct 48 ms 110980 KB Output is correct
14 Correct 50 ms 111000 KB Output is correct
15 Correct 49 ms 110916 KB Output is correct
16 Correct 48 ms 110864 KB Output is correct
17 Correct 50 ms 110908 KB Output is correct
18 Correct 50 ms 110844 KB Output is correct
19 Correct 51 ms 110916 KB Output is correct
20 Correct 55 ms 110944 KB Output is correct
21 Correct 44 ms 106044 KB Output is correct
22 Correct 45 ms 108380 KB Output is correct
23 Correct 51 ms 110724 KB Output is correct
24 Correct 49 ms 110824 KB Output is correct
25 Correct 56 ms 110920 KB Output is correct
26 Correct 51 ms 111296 KB Output is correct
27 Correct 44 ms 106216 KB Output is correct
28 Correct 49 ms 110932 KB Output is correct
29 Correct 54 ms 111032 KB Output is correct
30 Correct 48 ms 110920 KB Output is correct
31 Correct 3375 ms 758748 KB Output is correct
32 Correct 278 ms 111624 KB Output is correct
33 Correct 2801 ms 756000 KB Output is correct
34 Correct 3324 ms 754772 KB Output is correct
35 Correct 3227 ms 765676 KB Output is correct
36 Correct 2917 ms 760652 KB Output is correct
37 Correct 2517 ms 762028 KB Output is correct
38 Correct 2144 ms 757720 KB Output is correct
39 Correct 1558 ms 759860 KB Output is correct
40 Correct 1642 ms 758456 KB Output is correct
41 Correct 2187 ms 760100 KB Output is correct
42 Correct 2078 ms 763912 KB Output is correct
43 Correct 103 ms 112704 KB Output is correct
44 Correct 2087 ms 759804 KB Output is correct
45 Correct 1862 ms 757392 KB Output is correct
46 Correct 1727 ms 756712 KB Output is correct
47 Correct 1043 ms 759536 KB Output is correct
48 Correct 1070 ms 758792 KB Output is correct
49 Correct 1230 ms 761736 KB Output is correct
50 Correct 1307 ms 766332 KB Output is correct
51 Correct 1282 ms 760952 KB Output is correct
52 Correct 778 ms 412564 KB Output is correct
53 Correct 780 ms 427772 KB Output is correct
54 Correct 1898 ms 765080 KB Output is correct
55 Correct 1820 ms 468376 KB Output is correct
56 Correct 1518 ms 428984 KB Output is correct
57 Correct 2407 ms 760816 KB Output is correct
58 Correct 1913 ms 469508 KB Output is correct
59 Correct 1514 ms 430836 KB Output is correct
60 Correct 2206 ms 763788 KB Output is correct
61 Correct 124 ms 117876 KB Output is correct
62 Correct 830 ms 412680 KB Output is correct
63 Correct 1421 ms 423336 KB Output is correct
64 Correct 1623 ms 462364 KB Output is correct
65 Correct 2153 ms 765836 KB Output is correct
66 Correct 2251 ms 763224 KB Output is correct
67 Correct 315 ms 123620 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 105928 KB Output is correct
2 Correct 41 ms 105952 KB Output is correct
3 Correct 42 ms 105932 KB Output is correct
4 Correct 44 ms 106412 KB Output is correct
5 Correct 44 ms 106024 KB Output is correct
6 Correct 56 ms 115904 KB Output is correct
7 Correct 45 ms 108380 KB Output is correct
8 Correct 50 ms 110776 KB Output is correct
9 Correct 49 ms 108376 KB Output is correct
10 Correct 59 ms 115648 KB Output is correct
11 Correct 51 ms 110992 KB Output is correct
12 Correct 56 ms 115960 KB Output is correct
13 Correct 48 ms 110980 KB Output is correct
14 Correct 50 ms 111000 KB Output is correct
15 Correct 49 ms 110916 KB Output is correct
16 Correct 48 ms 110864 KB Output is correct
17 Correct 50 ms 110908 KB Output is correct
18 Correct 50 ms 110844 KB Output is correct
19 Correct 51 ms 110916 KB Output is correct
20 Correct 55 ms 110944 KB Output is correct
21 Correct 44 ms 106044 KB Output is correct
22 Correct 45 ms 108380 KB Output is correct
23 Correct 51 ms 110724 KB Output is correct
24 Correct 49 ms 110824 KB Output is correct
25 Correct 56 ms 110920 KB Output is correct
26 Correct 51 ms 111296 KB Output is correct
27 Correct 44 ms 106216 KB Output is correct
28 Correct 49 ms 110932 KB Output is correct
29 Correct 54 ms 111032 KB Output is correct
30 Correct 48 ms 110920 KB Output is correct
31 Correct 3375 ms 758748 KB Output is correct
32 Correct 278 ms 111624 KB Output is correct
33 Correct 2801 ms 756000 KB Output is correct
34 Correct 3324 ms 754772 KB Output is correct
35 Correct 3227 ms 765676 KB Output is correct
36 Correct 2917 ms 760652 KB Output is correct
37 Correct 2517 ms 762028 KB Output is correct
38 Correct 2144 ms 757720 KB Output is correct
39 Correct 1558 ms 759860 KB Output is correct
40 Correct 1642 ms 758456 KB Output is correct
41 Correct 2187 ms 760100 KB Output is correct
42 Correct 2078 ms 763912 KB Output is correct
43 Correct 103 ms 112704 KB Output is correct
44 Correct 2087 ms 759804 KB Output is correct
45 Correct 1862 ms 757392 KB Output is correct
46 Correct 1727 ms 756712 KB Output is correct
47 Correct 1043 ms 759536 KB Output is correct
48 Correct 1070 ms 758792 KB Output is correct
49 Correct 1230 ms 761736 KB Output is correct
50 Correct 1307 ms 766332 KB Output is correct
51 Correct 1282 ms 760952 KB Output is correct
52 Correct 1153 ms 198356 KB Output is correct
53 Correct 917 ms 200096 KB Output is correct
54 Correct 924 ms 183116 KB Output is correct
55 Correct 1147 ms 195028 KB Output is correct
56 Correct 814 ms 199600 KB Output is correct
57 Correct 895 ms 200016 KB Output is correct
58 Correct 773 ms 183032 KB Output is correct
59 Correct 1016 ms 194616 KB Output is correct
60 Correct 1058 ms 199716 KB Output is correct
61 Correct 983 ms 201428 KB Output is correct
62 Correct 695 ms 198628 KB Output is correct
63 Correct 828 ms 200632 KB Output is correct
64 Runtime error 1332 ms 411416 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -