oj.uz

Submission #258468

# Submission time Handle Problem Language Result Execution time Memory
258468 2020-08-06T01:10:03 Z amoo_safar New Home (APIO18_new_home) C++17
80 / 100
 5000 ms 125076 KB 
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
 
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,fma,tune=native")
#pragma GCC optimize("unroll-loops")
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
 
typedef pair<int, int> pii;
 
const int N = 3e5 + 10;
const int Inf = 1e9;
 
int n, q, k;
int x[N], t[N], a[N], b[N];
int y[N], c[N], ans[N];
 
vector<int> V;
 

//map<int, int> mp[N];
set<int> rec[N];
 
const int SGN = (1 << 19);
int seg[SGN << 1];
/*
void Ins(int id, int l, int r, int x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		seg[id].insert(x);
		return ;
	}
	int mid = (L + R) >> 1;
	Ins(id << 1, l, r, x, L, mid);
	Ins(id << 1 | 1, l, r, x, mid, R);
}
void Rem(int id, int l, int r, int x, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		seg[id].erase(seg[id].find(x));
		return ;
	}
	int mid = (L + R) >> 1;
	Rem(id << 1, l, r, x, L, mid);
	Rem(id << 1 | 1, l, r, x, mid, R);
}
*/
inline int FastMin(int &a, int &b){
	return a < b ? a : b;
}
void Set(int idx, int v){
	idx += SGN;
	seg[idx] = v;
	while(idx >>= 1){
		seg[idx] = FastMin(seg[idx << 1], seg[idx << 1 | 1]);
	}
	/*if(R - L == 1){
		seg[id] = v;
		return ;
	}
	int mid = (L + R) >> 1;
	if(idx < mid) Set(id << 1, idx, v, L, mid);
	else Set(id << 1 | 1, idx, v, mid, R);
	seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
	*/
}
void SuperSet2(int idx, int v){
	idx += SGN;
	seg[idx] = v;
	while(seg[idx] < seg[idx ^ 1]) seg[idx >>= 1] = v;
}
void SuperSet(int idx, int v){
	idx += SGN;
	seg[idx] = v;
	while(seg[idx >>= 1] > v) seg[idx] = v;
}
 
 
int MN;
/*
int Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return Inf;
	if(l <= L && R <= r) return seg[id];
	
	int mid = (L + R) >> 1;
	return min(Get(id << 1, l, r, L, mid), Get(id << 1 | 1, l, r, mid, R));
	//if(idx < mid) Get(id << 1, idx, L, mid);
	//else Get(id << 1 | 1, idx, mid, R);
}
*/
 
int Get(int l){
	l += SGN;
	int r = SGN + SGN;
	int res = Inf;
	while(l ^ r){
		if(l & 1)
			res = min(res, seg[l ++]);
		l >>= 1; r >>= 1;
	}
	return res;
}
/*
template<typename T>
inline T Prev(T A){return --A; };
template<typename T>
inline T Next(T A){return ++A; };
*/
/*
pii GetRange(pii R){
	return pii(R.F, upper_bound(all(V), R.S) - V.begin());
}
*/
set<int>::iterator hint;
inline int GetRange(int tp){
	//set<int>::iterator it = hint;
	/*
	if(it == rec[tp].begin()) resL = 1;
	else resL = ( (*Prev(it)) + (*it)) / 2 + 1;
 	*/
	if(next(hint) == rec[tp].end()) return V.size();
	return upper_bound(all(V), ( (*next(hint)) + (*hint)) >> 1) - V.begin();
}
 
void SegGet(int qn){
	//cerr << "? " << pl << '\n';
	int pl = y[qn];
	//MN = Get(1, (lower_bound(all(V), pl) - V.begin()), V.size(), 0, SGN);
	MN = Get( lower_bound(all(V), pl) - V.begin() );
	//cerr << qn << ' ' << MN << '\n';
	ans[qn] = max(ans[qn], pl - MN);
	//if(CNT != k) return -1;
	//return max(MX - pl, pl - MN);
}
priority_queue<int, vector<int>, greater<int> > ms[N], msR[N];
 
inline void Norm(int idx){
	priority_queue<int, vector<int>, greater<int> > &AA = msR[idx];
	priority_queue<int, vector<int>, greater<int> > &BB = ms[idx];
	while(!AA.empty() && AA.top() == BB.top()){
		AA.pop();
		BB.pop();
	}
}
//multiset<int> ms[N];
inline void SegRem(int tp, int pl){
	int ran = GetRange(tp);
	
	if(ran == 0) return ;
	ran --;
	msR[ran].push(pl);
	if(ms[ran].top() == pl){
		Norm(ran);
	//ms[ran.S - 1].erase(ms[ran.S - 1].find(ran.F));
		Set(ran, (ms[ran].empty() ? Inf : ms[ran].top()));
	}
	//Rem(1, ran.F, ran.S, pl, 0, V.size());
}
inline void SegAdd(int tp, int pl){
	int ran = GetRange(tp);
	if(ran == 0) return ;
	ran --;
 
	ms[ran].push(pl);
	
	//if(ms[ran].top() == pl){
		//Norm(ran);
	//debug(ran.S - 1);
	SuperSet(ran, ms[ran].top());
	//Ins(1, ran.F, ran.S, pl, 0, V.size());
	//}
}
/*
inline void SegRemNoSet(int tp, int pl){
	int ran = GetRange(tp);
	
	if(ran == 0) return ;
	ran --;
	msR[ran].push(pl);
	Norm(ran);
	//ms[ran.S - 1].erase(ms[ran.S - 1].find(ran.F));
	//Set(ran, (ms[ran].empty() ? Inf : ms[ran].top()));
	//Rem(1, ran.F, ran.S, pl, 0, V.size());
}
*/
/*
inline void SegAddNoSet(int tp, int pl){
	int ran = GetRange(tp);
	if(ran == 0) return ;
	ran --;
 
	ms[ran].push(pl);
	//Norm(ran);
	//debug(ran.S - 1);
	//Set(ran, ms[ran].top());
	//Ins(1, ran.F, ran.S, pl, 0, V.size());
}
*/
void Add(int tp, int pl){
	//cerr << "+ " << tp << ' ' << pl << '\n';
	//mp[tp][pl] ++;
	//if(mp[tp][pl] > 1) return ;
 
	auto it = rec[tp].lower_bound(pl);
	int la = -1;
	//if(it != rec[tp].end()) nx = *it;
	if(it != rec[tp].begin()) la = *prev(it);
	//if(nx != -1) SegRem(tp, nx);
	if(la != -1){
		hint = prev(it);
		SegRem(tp, la);
 	}
	//rec[tp].insert(pl);
 	it = rec[tp].insert(it, pl);
	//if(nx != -1) SegAdd(tp, nx);
	//it = rec[tp].find(pl);
	if(la != -1){
		hint = prev(it);
		SegAdd(tp, la);
	}
	hint = it;
	SegAdd(tp, pl);
}
void Erase(int tp, int pl){
	//cerr << "- " << tp << ' ' << pl << '\n';
	//mp[tp][pl] --;
	//if(mp[tp][pl] > 0) return ;
 
	auto it = rec[tp].find(pl);
	int la = -1;
	
	//if(Next(it) != rec[tp].end()) nx = *Next(it);
	if(it != rec[tp].begin()){
		hint = prev(it);
		la = *hint;
	}
	//if(nx != -1) SegRem(tp, nx);
	if(la != -1){
		//hint = Prev(it);
		SegRem(tp, la);
	}

	hint = it;
	SegRem(tp, pl);
 
	it = rec[tp].erase(it);
	
	//if(nx != -1) SegAdd(tp, nx);
	if(la != -1){
		hint = --it;
		SegAdd(tp, la);
	}
}
 
vector<int> Ea[N], Er[N], Eq[N];
 
 
int flg[N], open[N], cntn;
 
vector<pii> Alt;
int Alti[N], cnti[N];

int main(){
	//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("Big.txt", "r", stdin);
	//freopen("Out.txt", "w", stdout);
 
	//clock_t StartTime = clock();
	scanf("%d%d%d", &n, &k, &q);

	//cin >> n >> k >> q;
	for(int i = 1; i <= n; i++){
		scanf("%d%d%d%d", x + i, t + i, a + i, b + i);
		Alt.pb({x[i], t[i]});
		//cin >> x[i] >> t[i] >> a[i] >> b[i];
		b[i] ++;
		//V.pb(a[i]); V.pb(b[i]);
	}
	sort(all(Alt)); Alt.resize(unique(all(Alt)) - Alt.begin());
	for(int i = 1; i <= n; i++)
		Alti[i] = lower_bound(all(Alt), pii(x[i], t[i])) - Alt.begin();

	for(int i = 1; i <= q; i++){
		scanf("%d%d", y + i, c + i);
		//cin >> y[i] >> c[i];
		V.pb(c[i]);
	}
 
	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	V.pb(1e8 + 1);
	int AllT = V.size();
	assert(AllT < N);
	for(int i = 1; i <= n; i++){
		a[i] = lower_bound(all(V), a[i]) - V.begin();
		b[i] = lower_bound(all(V), b[i]) - V.begin();
		Ea[a[i]].pb(i);
		Er[b[i]].pb(i);
		//cerr << "!!! " << a[i] << ' ' << b[i] << '\n';
	}
	for(int i = 1; i <= q; i++){
		c[i] = (lower_bound(all(V), c[i]) - V.begin() );
		Eq[c[i]].pb(i);
		//cerr << "? " << c[i] << '\n';
	}
 
	V.clear();
	//for(int i = 1; i <= n; i++) V.pb(x[i]);
	for(int i = 1; i <= q; i++) V.pb(y[i]);
	sort(all(V)); V.resize(unique(all(V)) - V.begin());
 
	memset(seg, 31, sizeof seg); seg[0] = -1;
 
	for(int tm = 0; tm < AllT; tm++){
		for(auto i : Ea[tm]){
			cnti[Alti[i]] ++;
			if(cnti[Alti[i]] == 1) Add(t[i], x[i]);
			open[t[i]] ++;
			if(open[t[i]] == 1) cntn ++;
		}
		for(auto i : Er[tm]){
			cnti[Alti[i]] --;
			if(cnti[Alti[i]] == 0) Erase(t[i], x[i]);
			open[t[i]] --;
			if(open[t[i]] == 0) cntn --;
		}
		for(auto i : Eq[tm]){
			SegGet(i);
			//cerr << i << ' ' << c
			if(cntn < k) flg[i] = true;
		}
		//cerr << '\n';
	}
	//if(n == 300000) assert(false);

	int SM = 100000001;
	for(int i = 1; i <= n; i ++) x[i] = SM - x[i];
	for(int i = 1; i <= q; i ++) y[i] = SM - y[i];
	for(auto &el : V)
		if(el < SM)
			el = SM - el;
	sort(all(V)); V.resize(unique(all(V)) - V.begin());
	
	memset(seg, 31, sizeof seg); seg[0] = -1;
	for(int tm = 0; tm < AllT; tm++){
		for(auto i : Ea[tm]){
			cnti[Alti[i]] ++;
			if(cnti[Alti[i]] == 1) Add(t[i], x[i]);
		}
		for(auto i : Er[tm]){
			cnti[Alti[i]] --;
			if(cnti[Alti[i]] == 0) Erase(t[i], x[i]);
		}
		for(auto i : Eq[tm])
			SegGet(i);
		//cerr << '\n';
	}
 	
 
 
	for(int i = 1; i <= q; i++) printf("%d\n", (flg[i] ? -1 : ans[i]) );
	
 
	//cerr << fixed << setprecision(4) << (double)(clock() - StartTime)/CLOCKS_PER_SEC << '\n';
	return 0;
}
/*
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
 
*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:277:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:281:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", x + i, t + i, a + i, b + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:292:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", y + i, c + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 58488 KB Output is correct
2 Correct 35 ms 58616 KB Output is correct
3 Correct 35 ms 58488 KB Output is correct
4 Correct 35 ms 58488 KB Output is correct
5 Correct 36 ms 58496 KB Output is correct
6 Correct 36 ms 58616 KB Output is correct
7 Correct 37 ms 58616 KB Output is correct
8 Correct 39 ms 58624 KB Output is correct
9 Correct 37 ms 58616 KB Output is correct
10 Correct 36 ms 58616 KB Output is correct
11 Correct 37 ms 58616 KB Output is correct
12 Correct 36 ms 58624 KB Output is correct
13 Correct 44 ms 58616 KB Output is correct
14 Correct 39 ms 58616 KB Output is correct
15 Correct 50 ms 58616 KB Output is correct
16 Correct 36 ms 58620 KB Output is correct
17 Correct 42 ms 58616 KB Output is correct
18 Correct 36 ms 58616 KB Output is correct
19 Correct 42 ms 58616 KB Output is correct
20 Correct 37 ms 58616 KB Output is correct
21 Correct 41 ms 58488 KB Output is correct
22 Correct 41 ms 58616 KB Output is correct
23 Correct 36 ms 58616 KB Output is correct
24 Correct 37 ms 58616 KB Output is correct
25 Correct 36 ms 58624 KB Output is correct
26 Correct 46 ms 58616 KB Output is correct
27 Correct 37 ms 58616 KB Output is correct
28 Correct 41 ms 58624 KB Output is correct
29 Correct 35 ms 58616 KB Output is correct
30 Correct 43 ms 58744 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 58488 KB Output is correct
2 Correct 35 ms 58616 KB Output is correct
3 Correct 35 ms 58488 KB Output is correct
4 Correct 35 ms 58488 KB Output is correct
5 Correct 36 ms 58496 KB Output is correct
6 Correct 36 ms 58616 KB Output is correct
7 Correct 37 ms 58616 KB Output is correct
8 Correct 39 ms 58624 KB Output is correct
9 Correct 37 ms 58616 KB Output is correct
10 Correct 36 ms 58616 KB Output is correct
11 Correct 37 ms 58616 KB Output is correct
12 Correct 36 ms 58624 KB Output is correct
13 Correct 44 ms 58616 KB Output is correct
14 Correct 39 ms 58616 KB Output is correct
15 Correct 50 ms 58616 KB Output is correct
16 Correct 36 ms 58620 KB Output is correct
17 Correct 42 ms 58616 KB Output is correct
18 Correct 36 ms 58616 KB Output is correct
19 Correct 42 ms 58616 KB Output is correct
20 Correct 37 ms 58616 KB Output is correct
21 Correct 41 ms 58488 KB Output is correct
22 Correct 41 ms 58616 KB Output is correct
23 Correct 36 ms 58616 KB Output is correct
24 Correct 37 ms 58616 KB Output is correct
25 Correct 36 ms 58624 KB Output is correct
26 Correct 46 ms 58616 KB Output is correct
27 Correct 37 ms 58616 KB Output is correct
28 Correct 41 ms 58624 KB Output is correct
29 Correct 35 ms 58616 KB Output is correct
30 Correct 43 ms 58744 KB Output is correct
31 Correct 664 ms 72176 KB Output is correct
32 Correct 104 ms 62192 KB Output is correct
33 Correct 637 ms 70284 KB Output is correct
34 Correct 625 ms 70508 KB Output is correct
35 Correct 692 ms 72176 KB Output is correct
36 Correct 651 ms 71932 KB Output is correct
37 Correct 452 ms 69744 KB Output is correct
38 Correct 471 ms 69448 KB Output is correct
39 Correct 367 ms 69360 KB Output is correct
40 Correct 391 ms 69280 KB Output is correct
41 Correct 429 ms 69104 KB Output is correct
42 Correct 444 ms 68976 KB Output is correct
43 Correct 101 ms 62452 KB Output is correct
44 Correct 380 ms 69076 KB Output is correct
45 Correct 371 ms 69016 KB Output is correct
46 Correct 405 ms 68848 KB Output is correct
47 Correct 234 ms 68080 KB Output is correct
48 Correct 232 ms 68592 KB Output is correct
49 Correct 266 ms 68336 KB Output is correct
50 Correct 281 ms 68336 KB Output is correct
51 Correct 273 ms 68588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2649 ms 117500 KB Output is correct
2 Correct 4191 ms 119824 KB Output is correct
3 Correct 1357 ms 105568 KB Output is correct
4 Correct 2339 ms 115784 KB Output is correct
5 Correct 3835 ms 119196 KB Output is correct
6 Correct 3972 ms 119128 KB Output is correct
7 Correct 1230 ms 105544 KB Output is correct
8 Correct 2013 ms 115164 KB Output is correct
9 Correct 2436 ms 119004 KB Output is correct
10 Correct 3274 ms 119848 KB Output is correct
11 Correct 1687 ms 118964 KB Output is correct
12 Correct 1763 ms 119904 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4298 ms 125076 KB Output is correct
2 Correct 331 ms 76196 KB Output is correct
3 Correct 4728 ms 123484 KB Output is correct
4 Correct 1772 ms 109916 KB Output is correct
5 Correct 3234 ms 121392 KB Output is correct
6 Correct 2884 ms 119888 KB Output is correct
7 Correct 4446 ms 122944 KB Output is correct
8 Correct 4657 ms 123368 KB Output is correct
9 Correct 1685 ms 109272 KB Output is correct
10 Correct 2786 ms 121392 KB Output is correct
11 Correct 3605 ms 124876 KB Output is correct
12 Correct 4132 ms 124440 KB Output is correct
13 Correct 1678 ms 121820 KB Output is correct
14 Correct 1606 ms 121308 KB Output is correct
15 Correct 1912 ms 122844 KB Output is correct
16 Correct 2069 ms 123236 KB Output is correct
17 Correct 1921 ms 122152 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 58488 KB Output is correct
2 Correct 35 ms 58616 KB Output is correct
3 Correct 35 ms 58488 KB Output is correct
4 Correct 35 ms 58488 KB Output is correct
5 Correct 36 ms 58496 KB Output is correct
6 Correct 36 ms 58616 KB Output is correct
7 Correct 37 ms 58616 KB Output is correct
8 Correct 39 ms 58624 KB Output is correct
9 Correct 37 ms 58616 KB Output is correct
10 Correct 36 ms 58616 KB Output is correct
11 Correct 37 ms 58616 KB Output is correct
12 Correct 36 ms 58624 KB Output is correct
13 Correct 44 ms 58616 KB Output is correct
14 Correct 39 ms 58616 KB Output is correct
15 Correct 50 ms 58616 KB Output is correct
16 Correct 36 ms 58620 KB Output is correct
17 Correct 42 ms 58616 KB Output is correct
18 Correct 36 ms 58616 KB Output is correct
19 Correct 42 ms 58616 KB Output is correct
20 Correct 37 ms 58616 KB Output is correct
21 Correct 41 ms 58488 KB Output is correct
22 Correct 41 ms 58616 KB Output is correct
23 Correct 36 ms 58616 KB Output is correct
24 Correct 37 ms 58616 KB Output is correct
25 Correct 36 ms 58624 KB Output is correct
26 Correct 46 ms 58616 KB Output is correct
27 Correct 37 ms 58616 KB Output is correct
28 Correct 41 ms 58624 KB Output is correct
29 Correct 35 ms 58616 KB Output is correct
30 Correct 43 ms 58744 KB Output is correct
31 Correct 664 ms 72176 KB Output is correct
32 Correct 104 ms 62192 KB Output is correct
33 Correct 637 ms 70284 KB Output is correct
34 Correct 625 ms 70508 KB Output is correct
35 Correct 692 ms 72176 KB Output is correct
36 Correct 651 ms 71932 KB Output is correct
37 Correct 452 ms 69744 KB Output is correct
38 Correct 471 ms 69448 KB Output is correct
39 Correct 367 ms 69360 KB Output is correct
40 Correct 391 ms 69280 KB Output is correct
41 Correct 429 ms 69104 KB Output is correct
42 Correct 444 ms 68976 KB Output is correct
43 Correct 101 ms 62452 KB Output is correct
44 Correct 380 ms 69076 KB Output is correct
45 Correct 371 ms 69016 KB Output is correct
46 Correct 405 ms 68848 KB Output is correct
47 Correct 234 ms 68080 KB Output is correct
48 Correct 232 ms 68592 KB Output is correct
49 Correct 266 ms 68336 KB Output is correct
50 Correct 281 ms 68336 KB Output is correct
51 Correct 273 ms 68588 KB Output is correct
52 Correct 303 ms 68848 KB Output is correct
53 Correct 329 ms 67604 KB Output is correct
54 Correct 435 ms 71152 KB Output is correct
55 Correct 354 ms 69620 KB Output is correct
56 Correct 329 ms 69748 KB Output is correct
57 Correct 374 ms 69232 KB Output is correct
58 Correct 411 ms 69568 KB Output is correct
59 Correct 368 ms 69876 KB Output is correct
60 Correct 386 ms 69360 KB Output is correct
61 Correct 120 ms 66032 KB Output is correct
62 Correct 356 ms 68732 KB Output is correct
63 Correct 388 ms 70256 KB Output is correct
64 Correct 511 ms 70128 KB Output is correct
65 Correct 458 ms 69488 KB Output is correct
66 Correct 421 ms 69252 KB Output is correct
67 Correct 206 ms 65012 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 58488 KB Output is correct
2 Correct 35 ms 58616 KB Output is correct
3 Correct 35 ms 58488 KB Output is correct
4 Correct 35 ms 58488 KB Output is correct
5 Correct 36 ms 58496 KB Output is correct
6 Correct 36 ms 58616 KB Output is correct
7 Correct 37 ms 58616 KB Output is correct
8 Correct 39 ms 58624 KB Output is correct
9 Correct 37 ms 58616 KB Output is correct
10 Correct 36 ms 58616 KB Output is correct
11 Correct 37 ms 58616 KB Output is correct
12 Correct 36 ms 58624 KB Output is correct
13 Correct 44 ms 58616 KB Output is correct
14 Correct 39 ms 58616 KB Output is correct
15 Correct 50 ms 58616 KB Output is correct
16 Correct 36 ms 58620 KB Output is correct
17 Correct 42 ms 58616 KB Output is correct
18 Correct 36 ms 58616 KB Output is correct
19 Correct 42 ms 58616 KB Output is correct
20 Correct 37 ms 58616 KB Output is correct
21 Correct 41 ms 58488 KB Output is correct
22 Correct 41 ms 58616 KB Output is correct
23 Correct 36 ms 58616 KB Output is correct
24 Correct 37 ms 58616 KB Output is correct
25 Correct 36 ms 58624 KB Output is correct
26 Correct 46 ms 58616 KB Output is correct
27 Correct 37 ms 58616 KB Output is correct
28 Correct 41 ms 58624 KB Output is correct
29 Correct 35 ms 58616 KB Output is correct
30 Correct 43 ms 58744 KB Output is correct
31 Correct 664 ms 72176 KB Output is correct
32 Correct 104 ms 62192 KB Output is correct
33 Correct 637 ms 70284 KB Output is correct
34 Correct 625 ms 70508 KB Output is correct
35 Correct 692 ms 72176 KB Output is correct
36 Correct 651 ms 71932 KB Output is correct
37 Correct 452 ms 69744 KB Output is correct
38 Correct 471 ms 69448 KB Output is correct
39 Correct 367 ms 69360 KB Output is correct
40 Correct 391 ms 69280 KB Output is correct
41 Correct 429 ms 69104 KB Output is correct
42 Correct 444 ms 68976 KB Output is correct
43 Correct 101 ms 62452 KB Output is correct
44 Correct 380 ms 69076 KB Output is correct
45 Correct 371 ms 69016 KB Output is correct
46 Correct 405 ms 68848 KB Output is correct
47 Correct 234 ms 68080 KB Output is correct
48 Correct 232 ms 68592 KB Output is correct
49 Correct 266 ms 68336 KB Output is correct
50 Correct 281 ms 68336 KB Output is correct
51 Correct 273 ms 68588 KB Output is correct
52 Correct 2649 ms 117500 KB Output is correct
53 Correct 4191 ms 119824 KB Output is correct
54 Correct 1357 ms 105568 KB Output is correct
55 Correct 2339 ms 115784 KB Output is correct
56 Correct 3835 ms 119196 KB Output is correct
57 Correct 3972 ms 119128 KB Output is correct
58 Correct 1230 ms 105544 KB Output is correct
59 Correct 2013 ms 115164 KB Output is correct
60 Correct 2436 ms 119004 KB Output is correct
61 Correct 3274 ms 119848 KB Output is correct
62 Correct 1687 ms 118964 KB Output is correct
63 Correct 1763 ms 119904 KB Output is correct
64 Correct 4298 ms 125076 KB Output is correct
65 Correct 331 ms 76196 KB Output is correct
66 Correct 4728 ms 123484 KB Output is correct
67 Correct 1772 ms 109916 KB Output is correct
68 Correct 3234 ms 121392 KB Output is correct
69 Correct 2884 ms 119888 KB Output is correct
70 Correct 4446 ms 122944 KB Output is correct
71 Correct 4657 ms 123368 KB Output is correct
72 Correct 1685 ms 109272 KB Output is correct
73 Correct 2786 ms 121392 KB Output is correct
74 Correct 3605 ms 124876 KB Output is correct
75 Correct 4132 ms 124440 KB Output is correct
76 Correct 1678 ms 121820 KB Output is correct
77 Correct 1606 ms 121308 KB Output is correct
78 Correct 1912 ms 122844 KB Output is correct
79 Correct 2069 ms 123236 KB Output is correct
80 Correct 1921 ms 122152 KB Output is correct
81 Correct 303 ms 68848 KB Output is correct
82 Correct 329 ms 67604 KB Output is correct
83 Correct 435 ms 71152 KB Output is correct
84 Correct 354 ms 69620 KB Output is correct
85 Correct 329 ms 69748 KB Output is correct
86 Correct 374 ms 69232 KB Output is correct
87 Correct 411 ms 69568 KB Output is correct
88 Correct 368 ms 69876 KB Output is correct
89 Correct 386 ms 69360 KB Output is correct
90 Correct 120 ms 66032 KB Output is correct
91 Correct 356 ms 68732 KB Output is correct
92 Correct 388 ms 70256 KB Output is correct
93 Correct 511 ms 70128 KB Output is correct
94 Correct 458 ms 69488 KB Output is correct
95 Correct 421 ms 69252 KB Output is correct
96 Correct 206 ms 65012 KB Output is correct
97 Correct 1985 ms 110836 KB Output is correct
98 Correct 354 ms 76764 KB Output is correct
99 Correct 4671 ms 116252 KB Output is correct
100 Correct 1943 ms 104544 KB Output is correct
101 Correct 3014 ms 120824 KB Output is correct
102 Execution timed out 5069 ms 122864 KB Time limit exceeded
103 Halted 0 ms 0 KB -