Submission #877101

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
877101	2023-11-22T21:32:33 Z	maroonrk	Overtaking (IOI23_overtaking)	C++17	100 / 100	661 ms	74988 KB

overtaking

#include "overtaking.h"

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t,class u>
int lwb(const vc<t>&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S,class F>
void soin(S&s,F&&f){
	sort(all(s),forward<F>(f));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}

template<class t,class u>
void fila(vc<t>&vs,const u&a){
	fill(all(vs),a);
}

bool dbg=false;
int sgn(__int128_t a){
	return a>0?1:(a<0?-1:0);
}

__int128_t crs(pi a,pi b){
	return (__int128_t)a.a*b.b-(__int128_t)a.b*b.a;
}

int ccw(pi a,pi b){
	return sgn(crs(a,b));
}

int ccw(pi a,pi b,pi c){
	return sgn(crs(b-a,c-a));
}

//x 座標の昇順に追加しているとして，上に凸になるようにしている
void add_convex(vc<pi>&ps,pi v){
	while(si(ps)>=2&&ccw(ps[si(ps)-2],ps[si(ps)-1],v)>=0)ps.pop_back();
	ps.pb(v);
}

//f(lw)=true,f(up)=false
template<class F>
int find_max_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))lw=mid;
		else up=mid;
	}
	return lw;
}

ll fdiv(ll a, ll b) { // floored division
	return a / b - ((a ^ b) < 0 && a % b); }

ll cdiv(ll a, ll b) { // ceiled division
	return a / b + ((a ^ b) > 0 && a % b); }

vi pos;
struct Convex{
	int cur,lasts;
	vc<pi> xy;
	Convex(int cc):cur(cc),lasts(-1){}
	void add_point(pi p){
		assert(lasts<=p.a);
		lasts=p.a;
		
		add_convex(xy,p);
	}
	int sub(int x)const{
		assert(si(xy));
		int p=find_max_true(0,si(xy),[&](int i){
			return xy[i-1].a+xy[i-1].b*x<xy[i].a+xy[i].b*x;
		});
		return xy[p].a+xy[p].b*x;
	}
	pi query(int z)const{
		assert(lasts<z);
		if(xy.empty())return pi(inf,z);
		int p=find_max_true(0,si(xy),[&](int i){
			return ccw(xy[i-1],xy[i],pi(z,0))<0;
		});
		int x=cdiv(z-xy[p].a,xy[p].b);
		int use=lwb(pos,pos[cur]+x);
		if(use==si(pos))return pi(inf,z);
		return pi(use,sub(pos[use]-pos[cur]));
	}
};

vvc<pi> ls;
vvc<int> ss;
vvc<int> memo;

int getans(const Convex&c,int s){
	auto [k,u]=c.query(s);
	if(k<si(memo)){
		return memo[k][lwb(ss[k],u)];
	}else{
		assert(u==s);
		return u;
	}
}

vc<Convex> cs;
int off;

void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S){
	off=(int)L*X;
	pb(pos,S);
	ls.resize(M+1);
	rep(i,N)if(W[i]>X){
		ls[0].eb(T[i],W[i]-X);
	}
	ss.resize(M+1);
	rep(i,M+1){
		soin(ls[i]);
		vc<pi> tmp;
		if(i+1<M){
			int mx=-inf;
			for(auto [s,t]:ls[i]){
				int u=s+t*(pos[i+1]-pos[i]);
				if(chmax(mx,u)){
					tmp.eb(s,t);
					ss[i+1].pb(u);
				}
				ls[i+1].eb(mx,t);
			}
		}
		ls[i].swap(tmp);
	}
	memo.resize(M+1);
	gnr(i,1,M+1){
		memo[i].resize(si(ss[i]));
		Convex c(i);
		int head=0;
		rep(j,si(ss[i])){
			int s=ss[i][j];
			while(head<si(ls[i])&&ls[i][head].a<s){
				c.add_point(ls[i][head++]);
			}
			memo[i][j]=getans(c,s);
		}
	}
	
	cs.eb(0);
	for(auto p:ls[0]){
		cs.pb(cs.back());
		cs.back().add_point(p);
	}
	
    return;
}

long long arrival_time(long long Y){
	int i=lwb(ls[0],pi(Y,-1));
	return getans(cs[i],Y)+off;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	448 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	600 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	856 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	1 ms	860 KB	Output is correct
14	Correct	1 ms	820 KB	Output is correct
15	Correct	2 ms	600 KB	Output is correct
16	Correct	2 ms	860 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	2 ms	860 KB	Output is correct
19	Correct	2 ms	604 KB	Output is correct
20	Correct	2 ms	604 KB	Output is correct
21	Correct	1 ms	604 KB	Output is correct
22	Correct	1 ms	604 KB	Output is correct
23	Correct	2 ms	604 KB	Output is correct
24	Correct	2 ms	756 KB	Output is correct
25	Correct	2 ms	604 KB	Output is correct
26	Correct	2 ms	668 KB	Output is correct
27	Correct	2 ms	604 KB	Output is correct
28	Correct	1 ms	604 KB	Output is correct
29	Correct	1 ms	684 KB	Output is correct
30	Correct	1 ms	604 KB	Output is correct
31	Correct	1 ms	696 KB	Output is correct
32	Correct	1 ms	860 KB	Output is correct
33	Correct	1 ms	860 KB	Output is correct
34	Correct	1 ms	860 KB	Output is correct
35	Correct	1 ms	860 KB	Output is correct
36	Correct	1 ms	696 KB	Output is correct
37	Correct	1 ms	860 KB	Output is correct
38	Correct	0 ms	440 KB	Output is correct
39	Correct	1 ms	348 KB	Output is correct
40	Correct	1 ms	860 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	448 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	600 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	856 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	2 ms	604 KB	Output is correct
20	Correct	1 ms	860 KB	Output is correct
21	Correct	1 ms	820 KB	Output is correct
22	Correct	2 ms	600 KB	Output is correct
23	Correct	2 ms	860 KB	Output is correct
24	Correct	2 ms	604 KB	Output is correct
25	Correct	2 ms	860 KB	Output is correct
26	Correct	2 ms	604 KB	Output is correct
27	Correct	2 ms	604 KB	Output is correct
28	Correct	1 ms	604 KB	Output is correct
29	Correct	1 ms	604 KB	Output is correct
30	Correct	2 ms	604 KB	Output is correct
31	Correct	2 ms	756 KB	Output is correct
32	Correct	2 ms	604 KB	Output is correct
33	Correct	2 ms	668 KB	Output is correct
34	Correct	2 ms	604 KB	Output is correct
35	Correct	1 ms	604 KB	Output is correct
36	Correct	1 ms	684 KB	Output is correct
37	Correct	1 ms	604 KB	Output is correct
38	Correct	1 ms	696 KB	Output is correct
39	Correct	1 ms	860 KB	Output is correct
40	Correct	1 ms	860 KB	Output is correct
41	Correct	1 ms	860 KB	Output is correct
42	Correct	1 ms	860 KB	Output is correct
43	Correct	1 ms	696 KB	Output is correct
44	Correct	1 ms	860 KB	Output is correct
45	Correct	0 ms	440 KB	Output is correct
46	Correct	1 ms	348 KB	Output is correct
47	Correct	1 ms	860 KB	Output is correct
48	Correct	150 ms	32036 KB	Output is correct
49	Correct	155 ms	32340 KB	Output is correct
50	Correct	162 ms	32568 KB	Output is correct
51	Correct	161 ms	32340 KB	Output is correct
52	Correct	155 ms	32340 KB	Output is correct
53	Correct	154 ms	32280 KB	Output is correct
54	Correct	163 ms	32312 KB	Output is correct
55	Correct	102 ms	27296 KB	Output is correct
56	Correct	154 ms	32344 KB	Output is correct
57	Correct	143 ms	32020 KB	Output is correct
58	Correct	154 ms	32428 KB	Output is correct
59	Correct	153 ms	32336 KB	Output is correct
60	Correct	154 ms	32300 KB	Output is correct
61	Correct	153 ms	32340 KB	Output is correct
62	Correct	2 ms	600 KB	Output is correct
63	Correct	2 ms	604 KB	Output is correct
64	Correct	73 ms	16432 KB	Output is correct
65	Correct	77 ms	16404 KB	Output is correct
66	Correct	120 ms	32068 KB	Output is correct
67	Correct	152 ms	32220 KB	Output is correct
68	Correct	141 ms	32156 KB	Output is correct
69	Correct	62 ms	32852 KB	Output is correct
70	Correct	66 ms	32852 KB	Output is correct
71	Correct	73 ms	32852 KB	Output is correct
72	Correct	105 ms	32860 KB	Output is correct
73	Correct	72 ms	32692 KB	Output is correct
74	Correct	78 ms	32852 KB	Output is correct
75	Correct	1 ms	604 KB	Output is correct
76	Correct	2 ms	604 KB	Output is correct
77	Correct	1 ms	604 KB	Output is correct
78	Correct	86 ms	32604 KB	Output is correct

Subtask #5

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	448 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	600 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	600 KB	Output is correct
20	Correct	1 ms	604 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	856 KB	Output is correct
28	Correct	2 ms	604 KB	Output is correct
29	Correct	1 ms	604 KB	Output is correct
30	Correct	2 ms	604 KB	Output is correct
31	Correct	1 ms	860 KB	Output is correct
32	Correct	1 ms	820 KB	Output is correct
33	Correct	2 ms	600 KB	Output is correct
34	Correct	2 ms	860 KB	Output is correct
35	Correct	2 ms	604 KB	Output is correct
36	Correct	2 ms	860 KB	Output is correct
37	Correct	2 ms	604 KB	Output is correct
38	Correct	2 ms	604 KB	Output is correct
39	Correct	1 ms	604 KB	Output is correct
40	Correct	1 ms	604 KB	Output is correct
41	Correct	2 ms	604 KB	Output is correct
42	Correct	2 ms	756 KB	Output is correct
43	Correct	2 ms	604 KB	Output is correct
44	Correct	2 ms	668 KB	Output is correct
45	Correct	2 ms	604 KB	Output is correct
46	Correct	1 ms	604 KB	Output is correct
47	Correct	1 ms	684 KB	Output is correct
48	Correct	1 ms	604 KB	Output is correct
49	Correct	1 ms	696 KB	Output is correct
50	Correct	1 ms	860 KB	Output is correct
51	Correct	1 ms	860 KB	Output is correct
52	Correct	1 ms	860 KB	Output is correct
53	Correct	1 ms	860 KB	Output is correct
54	Correct	1 ms	696 KB	Output is correct
55	Correct	1 ms	860 KB	Output is correct
56	Correct	0 ms	440 KB	Output is correct
57	Correct	1 ms	348 KB	Output is correct
58	Correct	1 ms	860 KB	Output is correct
59	Correct	150 ms	32036 KB	Output is correct
60	Correct	155 ms	32340 KB	Output is correct
61	Correct	162 ms	32568 KB	Output is correct
62	Correct	161 ms	32340 KB	Output is correct
63	Correct	155 ms	32340 KB	Output is correct
64	Correct	154 ms	32280 KB	Output is correct
65	Correct	163 ms	32312 KB	Output is correct
66	Correct	102 ms	27296 KB	Output is correct
67	Correct	154 ms	32344 KB	Output is correct
68	Correct	143 ms	32020 KB	Output is correct
69	Correct	154 ms	32428 KB	Output is correct
70	Correct	153 ms	32336 KB	Output is correct
71	Correct	154 ms	32300 KB	Output is correct
72	Correct	153 ms	32340 KB	Output is correct
73	Correct	2 ms	600 KB	Output is correct
74	Correct	2 ms	604 KB	Output is correct
75	Correct	73 ms	16432 KB	Output is correct
76	Correct	77 ms	16404 KB	Output is correct
77	Correct	120 ms	32068 KB	Output is correct
78	Correct	152 ms	32220 KB	Output is correct
79	Correct	141 ms	32156 KB	Output is correct
80	Correct	62 ms	32852 KB	Output is correct
81	Correct	66 ms	32852 KB	Output is correct
82	Correct	73 ms	32852 KB	Output is correct
83	Correct	105 ms	32860 KB	Output is correct
84	Correct	72 ms	32692 KB	Output is correct
85	Correct	78 ms	32852 KB	Output is correct
86	Correct	1 ms	604 KB	Output is correct
87	Correct	2 ms	604 KB	Output is correct
88	Correct	1 ms	604 KB	Output is correct
89	Correct	86 ms	32604 KB	Output is correct
90	Correct	192 ms	35192 KB	Output is correct
91	Correct	429 ms	67012 KB	Output is correct
92	Correct	454 ms	66816 KB	Output is correct
93	Correct	448 ms	67240 KB	Output is correct
94	Correct	436 ms	67156 KB	Output is correct
95	Correct	442 ms	67004 KB	Output is correct
96	Correct	431 ms	67248 KB	Output is correct
97	Correct	132 ms	30544 KB	Output is correct
98	Correct	429 ms	66936 KB	Output is correct
99	Correct	452 ms	67204 KB	Output is correct
100	Correct	451 ms	67140 KB	Output is correct
101	Correct	458 ms	66824 KB	Output is correct
102	Correct	438 ms	66864 KB	Output is correct
103	Correct	444 ms	67120 KB	Output is correct
104	Correct	363 ms	49188 KB	Output is correct
105	Correct	415 ms	53572 KB	Output is correct
106	Correct	454 ms	74988 KB	Output is correct
107	Correct	477 ms	74488 KB	Output is correct
108	Correct	487 ms	74820 KB	Output is correct
109	Correct	505 ms	74360 KB	Output is correct
110	Correct	489 ms	74580 KB	Output is correct
111	Correct	294 ms	67928 KB	Output is correct
112	Correct	307 ms	67920 KB	Output is correct
113	Correct	423 ms	68928 KB	Output is correct
114	Correct	581 ms	70176 KB	Output is correct
115	Correct	385 ms	67964 KB	Output is correct
116	Correct	350 ms	68824 KB	Output is correct
117	Correct	176 ms	39252 KB	Output is correct
118	Correct	202 ms	39504 KB	Output is correct
119	Correct	176 ms	37444 KB	Output is correct
120	Correct	197 ms	39504 KB	Output is correct
121	Correct	192 ms	40792 KB	Output is correct
122	Correct	427 ms	62032 KB	Output is correct
123	Correct	637 ms	70128 KB	Output is correct
124	Correct	598 ms	69968 KB	Output is correct
125	Correct	661 ms	69932 KB	Output is correct