oj.uz

Submission #108688

# Submission time Handle Problem Language Result Execution time Memory
108688 2019-05-01T04:29:46 Z ryansee New Home (APIO18_new_home) C++14
80 / 100
 4844 ms 131172 KB 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update> pbds_set;
#define llabs abs
#define sdb __attribute__((optimize("-Ofast"), target("arch=sandybridge")))
ll n, q, k;
tuple <ll, ll, ll, ll, ll> A[MAXN]; // l, type, a, b, i
spi Q[MAXN];
ll ans[MAXN];
multiset <ll> ms[MAXN];
priority_queue <pi, vector<pi>,greater<pi>> pq;
void st1_2() {
    sort(Q,Q+q); sort(A,A+n, [] (tuple<ll,ll,ll,ll,ll>x,tuple<ll,ll,ll,ll,ll>y) { return get<2>(x) < get<2>(y); });
	ll co = 0;
	FOR(i,0,q) {
		ll t = Q[i].f, l = Q[i].s.f, ind = Q[i].s.s;
		while(co < n && t >= get<2>(A[co])) {
			ms[get<1>(A[co])].ins(get<0>(A[co]));
			pq.ph(pi(get<3>(A[co]),co));++co;
		}
		while(pq.size() && pq.top().f < t) ms[get<1>(A[pq.top().s])].erase(ms[get<1>(A[pq.top().s])].find(get<0>(A[pq.top().s]))), pq.pop();
		ll anss = -1;
		FOR(i,1,k+1) {
			if(ms[i].empty()) { anss=INF; continue; }
			auto itr = ms[i].lower_bound(l);
			ll best = INF;
			if(itr != ms[i].end()) best=min(best, *itr-l);
			if(itr == ms[i].begin());
			else {
				--itr;
				best=min(best, l-*itr);
			}
// 			assert(best != LLINF);
			anss=max(anss,best);
		}
		if(anss==INF) anss=-1;
		ans[ind]=anss;
	}
	FOR(i,0,q) cout << ans[i] << '\n';
}
map <ll, ll> mp; // x, y
multiset<ll>types[MAXN];
ll STORECO[MAXN];
void check_removal_neg(map<ll,ll>::iterator itr) { 
	while(itr != mp.end()) {
			auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
			if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
			else { break; }
			assert(val == itr->f);
	}
}
void add_neg(ll xx, ll val) {
	mp[xx] = max(mp[xx],val); 
	auto itr = mp.lower_bound(xx);
	while(itr != mp.end()) {
			auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
			if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
			else { break; }
			assert(val == itr->f);
	}
	if(itr!=mp.begin())check_removal_neg(prev(itr));
	return;
}
bool remove_neg(ll &co, ll time) {
	while(co < n && get<3>(A[co]) < time) {
		ll l,type,a,b,ii; tie(l,type,a,b,ii)=A[co]; ++co;
		STORECO[type] --;
		if(STORECO[type] <= 0) return 0;
		auto itr = types[type].lower_bound(l);//assert(itr!=types[type].end());
		if(itr == types[type].begin()) {
		    assert(next(itr)!=types[type].end());
			add_neg(1, *next(itr)-1);
		} else if(next(itr) != types[type].end()) {
			add_neg(((*next(itr) + *prev(itr) + 1)/2), llabs( ((*next(itr) + *prev(itr) + 1)/2) - *next(itr) ));
		}
		types[type].erase(itr);
	}
	return 1;
}
void check_removal_pos(map<ll,ll>::iterator itr) {
	while(itr!=mp.begin()) {
			auto itr2 = prev(itr); ll val = itr->f;
			if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
			else break;
			assert(val==itr->f);
	}
	return;
}
void add_pos(ll xx, ll val) {
	mp[xx]=max(mp[xx],val);
	auto itr = mp.lower_bound(xx);
	while(itr!=mp.begin()) {
			auto itr2 = prev(itr); ll val = itr->f;
			if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
			else break;
			assert(val==itr->f);
	}
	if(next(itr) != mp.end()) check_removal_pos(next(itr));
	return;
}
bool remove_pos(ll &co, ll time) {
	while(co < n && get<3>(A[co]) < time) {
		ll l,type,a,b,ii; tie(l,type,a,b,ii)=A[co]; ++co;
		STORECO[type] --;
		if(STORECO[type]<=0) return 0;
		auto itr = types[type].lower_bound(l); //assert(itr!=types[type].end());
		if(itr == prev(types[type].end())) {
			add_pos(INF, INF-*prev(itr));
		} else if(itr != types[type].begin()) {
			add_pos(((*next(itr) + *prev(itr))/2), llabs( ((*next(itr) + *prev(itr))/2) - *prev(itr) ));
		}
		types[type].erase(itr);
	}	
	return 1;
}
void st3_4() {
	sort(Q,Q+q);
	sort(A,A+n,[](tuple<ll,ll,ll,ll,ll>x,tuple<ll,ll,ll,ll,ll>y) { return get<3>(x) < get<3>(y); });
	FOR(i,0,n) {
		types[get<1>(A[i])].ins(get<0>(A[i])); STORECO[get<1>(A[i])]++; // assert(!duplicate[get<0>(A[i])]); duplicate[get<0>(A[i])] = 1; 
	}
	FOR(K,1,k+1) {
		/*sort(all(types[K])); types[K].resize(unique(all(types[K]))-types[K].begin());*/ if(types[K].empty()) { FOR(i,0,q) cout << "-1\n"; exit(0); }
		for(auto i = next(types[K].begin()); i != types[K].end(); i++) {
			mp[(*i+*prev(i)+1)/2] = max(mp[(*i+*prev(i)+1)/2],llabs(*i-(*i+*prev(i)+1)/2));
		}
		mp[1]=max(mp[1],*types[K].begin()-1);
	}
	for(auto itr = mp.begin(); itr != mp.end(); itr ++) {
		while(itr != mp.end()) {
			auto itr2 = next(itr); if(itr2 == mp.end()) break; ll val = itr->f;
			if(itr->s - (itr2->f-itr->f) > itr2->s) itr = --mp.erase(itr2);
			else { break; }
			assert(val == itr->f);
		}
	}
	ll co = 0; bool stillcan = 1;
	FOR(i,0,q) { if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
		ll l = Q[i].s.f, t = Q[i].f; stillcan &= remove_neg(co,t); if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
		auto itr = mp.upper_bound(l);
		assert(itr != mp.begin()); // even if size is one, itr will be ms.end()
		--itr;
		ans[Q[i].s.s] = itr->s - (l-itr->f);
	}
	mp.clear(); mmst(STORECO,0); FOR(i,1,k+1) types[i].clear(); FOR(i,0,n) { types[get<1>(A[i])].ins(get<0>(A[i])); STORECO[get<1>(A[i])]++; }
	FOR(K,1,k+1) {
		for(auto i = types[K].begin(); i != prev(types[K].end()); i ++) {
			mp[(*i+*next(i))/2] = max(mp[(*i+*next(i))/2],llabs((*i+*next(i))/2-*i));
		}
		mp[INF]=max(mp[INF],INF-(*--types[K].end()));
	}
	for(auto itr = mp.begin(); itr != mp.end(); itr ++) {
		while(itr!=mp.begin()) {
			auto itr2 = prev(itr); ll val = itr->f;
			if(itr->s - (itr->f - itr2->f) > itr2->s) itr=mp.erase(itr2);
			else break;
			assert(val==itr->f);
		}
	}
	co = 0;stillcan = 1;
	FOR(i,0,q) { if(!stillcan) { ans[Q[i].s.s] = -INF; continue; }
		ll l = Q[i].s.f, t = Q[i].f; stillcan &= remove_pos(co,t); if(!stillcan) { ans[Q[i].s.s] = -INF; continue; } 
		auto itr = mp.lower_bound(l);
// 		assert(itr != mp.end());
		ans[Q[i].s.s] = max(ans[Q[i].s.s], itr->s - (itr->f-l));
	}
	FOR(i,0,q)if(ans[i]==-INF){ans[i]=-1;}
	FOR(i,0,q) cout << ans[i] << '\n';
}
ll rndm = 5;
// struct node {
// 	int s,e,m;
// 	pbds_set v;
// 	node *l, *r;
// 	node(ll _S, ll _E) {
// 		s = _S, e = _E, m = (s+e)/2;
// // 		v.clear();
// 		if(s!=e){
// 			l = new node(s,m);
// 			r = new node(m+1,e);
// 		}
// 	}
// 	void sdb open(ll x, ll nv) {
// 		v.ins(pi(nv,rndm++));
// 		if(s==e) return;
// 		if(x>m) r->open(x,nv);
// 		else l->open(x,nv);
// 	}
// 	void sdb close(ll x, ll nv) {
// 		v.erase(v.lower_bound(pi(nv,0)));
// 		if(s==e) return;
// 		if(x>m) r->close(x,nv);
// 		else l->close(x,nv);
// 	}
// 	ll sdb rmq(ll x, ll y, ll nv) {
// 		if(s==x&&e==y) { return val(nv); }
// 		if(x > m) return r->rmq(x,y,nv);
// 		else if(y <= m) return l->rmq(x,y,nv);
// 		else return l->rmq(x,m,nv) + r->rmq(m+1,y,nv);
// 	}
// 	inline ll sdb val(ll x) {
// 		return (v.order_of_key(pi(x,0)));
// 	}
// // 	void degug() {
// // 		if(v.empty()) return;
// // // 		if(s==e) { assert(siz(v)==1); cerr << s << ' ' << v[0] << '\n'; return; }
// // 		l->degug();
// // 		r->degug();
// // 	}
// } *seg;
pbds_set fw[MAXN];
void open(ll x, ll nv) {
	++ x;
	for(; x <= n; x+=x&(-x)) fw[x].ins(pi(nv,rndm++));
}
void close(ll x, ll nv) {
	++ x;
	for(; x <= n; x+=x&(-x)) fw[x].erase(fw[x].lower_bound(pi(nv,0)));
}
ll query(ll x, ll nv) {
    ll res = 0;
    for(; x; x-=x&(-x)) {
        res += fw[x].order_of_key(pi(nv,0));
    }
    return res;
}
ll rmq(ll x, ll y, ll nv) {
    ++x,++y;
    return query(y,nv) - query(x-1,nv);
}
vector<ll>d;
inline ll sdb solve5(ll l) {
	ll st = -1, en = max(d.back()-l+2,l-d[0]+2), mid = 0;
	while(en-st > 1) {
		mid = (st+en)>>1ll;
		ll lower = lbd(d,l-mid)-d.begin();
		ll upper = ubd(d,l+mid)-d.begin()-1;
		if(lower<=upper&&rmq(lower,upper,lower) >= k) en = mid;
		else st = mid;
	}
	return en;
}
inline void sdb rem(ll k, multiset<ll>::iterator itr) {
	if(itr == types[k].begin()||itr==types[k].end()) return; 
	close(*itr, *prev(itr));
}
inline void sdb add(ll k, multiset<ll>::iterator itr) {
	if(itr == types[k].begin()||itr==types[k].end()) return;
	open(*itr, *prev(itr));
}
inline void sdb st5() {
	sort(Q,Q+q);  FOR(i,0,n) d.pb(get<0>(A[i])); sort(all(d)); d.resize(unique(all(d))-d.begin());FOR(i,0,n) { get<4>(A[i]) = lbd(d,get<0>(A[i]))-d.begin(); }
	sort(A,A+n,[](tuple<ll,ll,ll,ll,ll>x,tuple<ll,ll,ll,ll,ll>y) { return get<2>(x) < get<2>(y); });
	ll co = 0; priority_queue <pi, vector<pi>, greater<pi>> ms; // seg = new node(0, n-1);
	FOR(i,1,k+1) types[i].ins(-INF);
	FOR(i,0,q) {
		ll t = Q[i].f, l = Q[i].s.f, ind = Q[i].s.s;
		while(co < n && get<2>(A[co]) <= t) {
		    if(get<3>(A[co]) < t) { ++co; continue; }
			ll type = get<1>(A[co]);
			ll i = get<4>(A[co]);
			auto itr = types[type].lower_bound(i);
			if(itr != types[type].end()) { rem(type, itr); }
			types[type].ins(i);
			itr = types[type].lower_bound(i);
			add(type, itr);
			add(type, next(itr));
			ms.ph(pi(get<3>(A[co]), co));
			++co;
		}
		while(ms.size() && ms.top().f < t) {
			ll i = get<4>(A[ms.top().s]);
			ll type = get<1>(A[ms.top().s]);
			ms.pop();
			auto itr = types[type].find(i); // assert(itr != types[type].begin()); 
			rem(type,itr); 
			rem(type,next(itr));
			itr = types[type].erase(types[type].find(i));
			add(type, itr);
		}
		ans[ind] = solve5(l);  if(ans[ind]==max(d.back()-l+2,l-d[0]+2)) ans[ind]=-1;
	}
	FOR(i,0,q) cout << ans[i] << '\n';
}
int sdb main()
{ // freopen("int","r",stdin);
	FAST
	cin>>n>>k>>q;
	FOR(i,0,n) {
		ll a,b,c,d;cin>>a>>b>>c>>d;
		A[i]=make_tuple(a,b,c,d,i);
	}
	FOR(i,0,q) {
		ll l,t;
		cin>>l>>t;
		Q[i]=spi(t,pi(l,i));
	}
	if(k<=400&&n<=6*1e4&&q<=6*1e4) { st1_2(); return 0; }
	else if(n > 6*((ll)1e4)) {
	    st3_4(); return 0;
	}
	else { st5(); }
}
/*
 * 
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
* 
* 
*
* to fit st3_4 sol *
4 2 4
3 1 1 10
9 2 1 4
7 2 1 7
4 1 1 10
5 3
5 6
5 9
1 10 
* 
*Ans:
* 2
* 2
* -1
* -1
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 56696 KB Output is correct
2 Correct 63 ms 56696 KB Output is correct
3 Correct 72 ms 56696 KB Output is correct
4 Correct 78 ms 56696 KB Output is correct
5 Correct 76 ms 56828 KB Output is correct
6 Correct 65 ms 56796 KB Output is correct
7 Correct 62 ms 56824 KB Output is correct
8 Correct 65 ms 56796 KB Output is correct
9 Correct 65 ms 56824 KB Output is correct
10 Correct 63 ms 56824 KB Output is correct
11 Correct 67 ms 56824 KB Output is correct
12 Correct 63 ms 56824 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 65 ms 56824 KB Output is correct
15 Correct 61 ms 56824 KB Output is correct
16 Correct 61 ms 56824 KB Output is correct
17 Correct 62 ms 56824 KB Output is correct
18 Correct 62 ms 56824 KB Output is correct
19 Correct 63 ms 56824 KB Output is correct
20 Correct 78 ms 56824 KB Output is correct
21 Correct 64 ms 56824 KB Output is correct
22 Correct 62 ms 56952 KB Output is correct
23 Correct 60 ms 56824 KB Output is correct
24 Correct 64 ms 56824 KB Output is correct
25 Correct 60 ms 56824 KB Output is correct
26 Correct 62 ms 56824 KB Output is correct
27 Correct 64 ms 56824 KB Output is correct
28 Correct 63 ms 56952 KB Output is correct
29 Correct 65 ms 56952 KB Output is correct
30 Correct 66 ms 56824 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 56696 KB Output is correct
2 Correct 63 ms 56696 KB Output is correct
3 Correct 72 ms 56696 KB Output is correct
4 Correct 78 ms 56696 KB Output is correct
5 Correct 76 ms 56828 KB Output is correct
6 Correct 65 ms 56796 KB Output is correct
7 Correct 62 ms 56824 KB Output is correct
8 Correct 65 ms 56796 KB Output is correct
9 Correct 65 ms 56824 KB Output is correct
10 Correct 63 ms 56824 KB Output is correct
11 Correct 67 ms 56824 KB Output is correct
12 Correct 63 ms 56824 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 65 ms 56824 KB Output is correct
15 Correct 61 ms 56824 KB Output is correct
16 Correct 61 ms 56824 KB Output is correct
17 Correct 62 ms 56824 KB Output is correct
18 Correct 62 ms 56824 KB Output is correct
19 Correct 63 ms 56824 KB Output is correct
20 Correct 78 ms 56824 KB Output is correct
21 Correct 64 ms 56824 KB Output is correct
22 Correct 62 ms 56952 KB Output is correct
23 Correct 60 ms 56824 KB Output is correct
24 Correct 64 ms 56824 KB Output is correct
25 Correct 60 ms 56824 KB Output is correct
26 Correct 62 ms 56824 KB Output is correct
27 Correct 64 ms 56824 KB Output is correct
28 Correct 63 ms 56952 KB Output is correct
29 Correct 65 ms 56952 KB Output is correct
30 Correct 66 ms 56824 KB Output is correct
31 Correct 2844 ms 68400 KB Output is correct
32 Correct 153 ms 63828 KB Output is correct
33 Correct 307 ms 65752 KB Output is correct
34 Correct 2226 ms 65900 KB Output is correct
35 Correct 1588 ms 68252 KB Output is correct
36 Correct 364 ms 68076 KB Output is correct
37 Correct 289 ms 64632 KB Output is correct
38 Correct 175 ms 64504 KB Output is correct
39 Correct 153 ms 64120 KB Output is correct
40 Correct 144 ms 64220 KB Output is correct
41 Correct 334 ms 64468 KB Output is correct
42 Correct 459 ms 64476 KB Output is correct
43 Correct 386 ms 67600 KB Output is correct
44 Correct 296 ms 64376 KB Output is correct
45 Correct 178 ms 64376 KB Output is correct
46 Correct 130 ms 64224 KB Output is correct
47 Correct 153 ms 63992 KB Output is correct
48 Correct 129 ms 63864 KB Output is correct
49 Correct 151 ms 63992 KB Output is correct
50 Correct 326 ms 64180 KB Output is correct
51 Correct 147 ms 63992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1425 ms 120212 KB Output is correct
2 Correct 1981 ms 122872 KB Output is correct
3 Correct 745 ms 105324 KB Output is correct
4 Correct 1274 ms 117952 KB Output is correct
5 Correct 2053 ms 122620 KB Output is correct
6 Correct 1692 ms 123128 KB Output is correct
7 Correct 386 ms 105308 KB Output is correct
8 Correct 1055 ms 117980 KB Output is correct
9 Correct 1506 ms 122376 KB Output is correct
10 Correct 1405 ms 123636 KB Output is correct
11 Correct 990 ms 122320 KB Output is correct
12 Correct 1232 ms 123576 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2344 ms 123308 KB Output is correct
2 Correct 894 ms 99108 KB Output is correct
3 Correct 3482 ms 122808 KB Output is correct
4 Correct 642 ms 103672 KB Output is correct
5 Correct 1329 ms 118568 KB Output is correct
6 Correct 1178 ms 116196 KB Output is correct
7 Correct 4248 ms 123256 KB Output is correct
8 Correct 3607 ms 122916 KB Output is correct
9 Correct 706 ms 104696 KB Output is correct
10 Correct 1533 ms 118848 KB Output is correct
11 Correct 2054 ms 122064 KB Output is correct
12 Correct 2751 ms 122652 KB Output is correct
13 Correct 1251 ms 120560 KB Output is correct
14 Correct 1357 ms 119820 KB Output is correct
15 Correct 1363 ms 120952 KB Output is correct
16 Correct 1998 ms 122116 KB Output is correct
17 Correct 1570 ms 120756 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 56696 KB Output is correct
2 Correct 63 ms 56696 KB Output is correct
3 Correct 72 ms 56696 KB Output is correct
4 Correct 78 ms 56696 KB Output is correct
5 Correct 76 ms 56828 KB Output is correct
6 Correct 65 ms 56796 KB Output is correct
7 Correct 62 ms 56824 KB Output is correct
8 Correct 65 ms 56796 KB Output is correct
9 Correct 65 ms 56824 KB Output is correct
10 Correct 63 ms 56824 KB Output is correct
11 Correct 67 ms 56824 KB Output is correct
12 Correct 63 ms 56824 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 65 ms 56824 KB Output is correct
15 Correct 61 ms 56824 KB Output is correct
16 Correct 61 ms 56824 KB Output is correct
17 Correct 62 ms 56824 KB Output is correct
18 Correct 62 ms 56824 KB Output is correct
19 Correct 63 ms 56824 KB Output is correct
20 Correct 78 ms 56824 KB Output is correct
21 Correct 64 ms 56824 KB Output is correct
22 Correct 62 ms 56952 KB Output is correct
23 Correct 60 ms 56824 KB Output is correct
24 Correct 64 ms 56824 KB Output is correct
25 Correct 60 ms 56824 KB Output is correct
26 Correct 62 ms 56824 KB Output is correct
27 Correct 64 ms 56824 KB Output is correct
28 Correct 63 ms 56952 KB Output is correct
29 Correct 65 ms 56952 KB Output is correct
30 Correct 66 ms 56824 KB Output is correct
31 Correct 2844 ms 68400 KB Output is correct
32 Correct 153 ms 63828 KB Output is correct
33 Correct 307 ms 65752 KB Output is correct
34 Correct 2226 ms 65900 KB Output is correct
35 Correct 1588 ms 68252 KB Output is correct
36 Correct 364 ms 68076 KB Output is correct
37 Correct 289 ms 64632 KB Output is correct
38 Correct 175 ms 64504 KB Output is correct
39 Correct 153 ms 64120 KB Output is correct
40 Correct 144 ms 64220 KB Output is correct
41 Correct 334 ms 64468 KB Output is correct
42 Correct 459 ms 64476 KB Output is correct
43 Correct 386 ms 67600 KB Output is correct
44 Correct 296 ms 64376 KB Output is correct
45 Correct 178 ms 64376 KB Output is correct
46 Correct 130 ms 64224 KB Output is correct
47 Correct 153 ms 63992 KB Output is correct
48 Correct 129 ms 63864 KB Output is correct
49 Correct 151 ms 63992 KB Output is correct
50 Correct 326 ms 64180 KB Output is correct
51 Correct 147 ms 63992 KB Output is correct
52 Correct 3371 ms 101956 KB Output is correct
53 Correct 2927 ms 80340 KB Output is correct
54 Correct 4844 ms 100000 KB Output is correct
55 Correct 2268 ms 77640 KB Output is correct
56 Correct 2370 ms 83760 KB Output is correct
57 Correct 1655 ms 69052 KB Output is correct
58 Correct 1965 ms 77736 KB Output is correct
59 Correct 2012 ms 83688 KB Output is correct
60 Correct 1887 ms 69156 KB Output is correct
61 Correct 873 ms 131172 KB Output is correct
62 Correct 3627 ms 101892 KB Output is correct
63 Correct 4611 ms 94812 KB Output is correct
64 Correct 4277 ms 88788 KB Output is correct
65 Correct 3097 ms 73116 KB Output is correct
66 Correct 1577 ms 65776 KB Output is correct
67 Correct 2659 ms 76872 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 56696 KB Output is correct
2 Correct 63 ms 56696 KB Output is correct
3 Correct 72 ms 56696 KB Output is correct
4 Correct 78 ms 56696 KB Output is correct
5 Correct 76 ms 56828 KB Output is correct
6 Correct 65 ms 56796 KB Output is correct
7 Correct 62 ms 56824 KB Output is correct
8 Correct 65 ms 56796 KB Output is correct
9 Correct 65 ms 56824 KB Output is correct
10 Correct 63 ms 56824 KB Output is correct
11 Correct 67 ms 56824 KB Output is correct
12 Correct 63 ms 56824 KB Output is correct
13 Correct 62 ms 56952 KB Output is correct
14 Correct 65 ms 56824 KB Output is correct
15 Correct 61 ms 56824 KB Output is correct
16 Correct 61 ms 56824 KB Output is correct
17 Correct 62 ms 56824 KB Output is correct
18 Correct 62 ms 56824 KB Output is correct
19 Correct 63 ms 56824 KB Output is correct
20 Correct 78 ms 56824 KB Output is correct
21 Correct 64 ms 56824 KB Output is correct
22 Correct 62 ms 56952 KB Output is correct
23 Correct 60 ms 56824 KB Output is correct
24 Correct 64 ms 56824 KB Output is correct
25 Correct 60 ms 56824 KB Output is correct
26 Correct 62 ms 56824 KB Output is correct
27 Correct 64 ms 56824 KB Output is correct
28 Correct 63 ms 56952 KB Output is correct
29 Correct 65 ms 56952 KB Output is correct
30 Correct 66 ms 56824 KB Output is correct
31 Correct 2844 ms 68400 KB Output is correct
32 Correct 153 ms 63828 KB Output is correct
33 Correct 307 ms 65752 KB Output is correct
34 Correct 2226 ms 65900 KB Output is correct
35 Correct 1588 ms 68252 KB Output is correct
36 Correct 364 ms 68076 KB Output is correct
37 Correct 289 ms 64632 KB Output is correct
38 Correct 175 ms 64504 KB Output is correct
39 Correct 153 ms 64120 KB Output is correct
40 Correct 144 ms 64220 KB Output is correct
41 Correct 334 ms 64468 KB Output is correct
42 Correct 459 ms 64476 KB Output is correct
43 Correct 386 ms 67600 KB Output is correct
44 Correct 296 ms 64376 KB Output is correct
45 Correct 178 ms 64376 KB Output is correct
46 Correct 130 ms 64224 KB Output is correct
47 Correct 153 ms 63992 KB Output is correct
48 Correct 129 ms 63864 KB Output is correct
49 Correct 151 ms 63992 KB Output is correct
50 Correct 326 ms 64180 KB Output is correct
51 Correct 147 ms 63992 KB Output is correct
52 Correct 1425 ms 120212 KB Output is correct
53 Correct 1981 ms 122872 KB Output is correct
54 Correct 745 ms 105324 KB Output is correct
55 Correct 1274 ms 117952 KB Output is correct
56 Correct 2053 ms 122620 KB Output is correct
57 Correct 1692 ms 123128 KB Output is correct
58 Correct 386 ms 105308 KB Output is correct
59 Correct 1055 ms 117980 KB Output is correct
60 Correct 1506 ms 122376 KB Output is correct
61 Correct 1405 ms 123636 KB Output is correct
62 Correct 990 ms 122320 KB Output is correct
63 Correct 1232 ms 123576 KB Output is correct
64 Correct 2344 ms 123308 KB Output is correct
65 Correct 894 ms 99108 KB Output is correct
66 Correct 3482 ms 122808 KB Output is correct
67 Correct 642 ms 103672 KB Output is correct
68 Correct 1329 ms 118568 KB Output is correct
69 Correct 1178 ms 116196 KB Output is correct
70 Correct 4248 ms 123256 KB Output is correct
71 Correct 3607 ms 122916 KB Output is correct
72 Correct 706 ms 104696 KB Output is correct
73 Correct 1533 ms 118848 KB Output is correct
74 Correct 2054 ms 122064 KB Output is correct
75 Correct 2751 ms 122652 KB Output is correct
76 Correct 1251 ms 120560 KB Output is correct
77 Correct 1357 ms 119820 KB Output is correct
78 Correct 1363 ms 120952 KB Output is correct
79 Correct 1998 ms 122116 KB Output is correct
80 Correct 1570 ms 120756 KB Output is correct
81 Correct 3371 ms 101956 KB Output is correct
82 Correct 2927 ms 80340 KB Output is correct
83 Correct 4844 ms 100000 KB Output is correct
84 Correct 2268 ms 77640 KB Output is correct
85 Correct 2370 ms 83760 KB Output is correct
86 Correct 1655 ms 69052 KB Output is correct
87 Correct 1965 ms 77736 KB Output is correct
88 Correct 2012 ms 83688 KB Output is correct
89 Correct 1887 ms 69156 KB Output is correct
90 Correct 873 ms 131172 KB Output is correct
91 Correct 3627 ms 101892 KB Output is correct
92 Correct 4611 ms 94812 KB Output is correct
93 Correct 4277 ms 88788 KB Output is correct
94 Correct 3097 ms 73116 KB Output is correct
95 Correct 1577 ms 65776 KB Output is correct
96 Correct 2659 ms 76872 KB Output is correct
97 Incorrect 651 ms 111620 KB Output isn't correct
98 Halted 0 ms 0 KB -