oj.uz

Submission #841235

# Submission time Handle Problem Language Result Execution time Memory
841235 2023-09-01T11:55:11 Z maroonrk Radio Towers (IOI22_towers) C++17
100 / 100
 1573 ms 152388 KB 
#include "towers.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>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t>
bool bis(const vc<t>&v,const t&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);
}

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

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

template<class S>
S revv(S s){
	reverse(all(s));
	return s;
}

pi operator+(pi a,pi b){return pi(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>
void pb(vc<t>&a,const vc<t>&b){
	a.insert(a.ed,all(b));
}

template<class t>
vc<t> cat(vc<t> a,const vc<t>&b){
	pb(a,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;
}

//N() が単位元
//VERIFY: yosupo
//CF407E
template<class N>
struct segtree{
	vc<N> x;
	int n,s;
	segtree(){}
	template<class t>
	segtree(const vc<t>&a){
		n=a.size();
		s=1;
		while(s<n){s*=2;}
		x.resize(s*2);
		rep(i,n)
			x[s+i]=N(a[i]);
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	//NOT Verified
	segtree(int nn){
		resize(nn);
	}
	void resize(int nn){
		n=nn;
		s=1;
		while(s<n){s*=2;}
		x.assign(s*2,N());
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	template<class t>
	void load(const vc<t>&a){
		n=a.size();
		s=1;
		while(s<n){s*=2;}
		x.resize(s*2);
		rep(i,n)
			x[s+i]=N(a[i]);
		rng(i,n,s)
			x[s+i]=N();
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void clear(){
		rep(i,n)
			x[s+i]=N();
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	N point_get(int i){
		assert(inc(0,i,n-1));
		return x[i+s];
	}
	void point_set(int i,const N&t){
		assert(inc(0,i,n-1));
		i+=s;
		x[i]=t;
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void point_merge(int i,const N&t){
		assert(inc(0,i,n-1));
		i+=s;
		x[i]=N::merge(x[i],t);
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	template<class F,class...Args>
	void point_change(int i,F f,Args&&...args){
		assert(inc(0,i,n-1));
		i+=s;
		(x[i].*f)(forward<Args>(args)...);
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	N composite(int b,int e){
		assert(0<=b&&b<=e&&e<=n);
		N lf,rt;
		for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){
			if (l&1){
				lf=N::merge(lf,x[l]);
				l++;
			}
			if (r&1){
				r--;
				rt=N::merge(x[r],rt);
			}
		}
		return N::merge(lf,rt);
	}
	N getall(){
		return x[1];
	}
	//UTPC2020E
	//n 超えるかもしれない
	template <class F,class... Args> 
	pair<int,N> max_right(int l,F f,Args&&... args){
		assert((N().*f)(forward<Args>(args)...));
		assert(0<=l&&l<=n);
		if(l==n)return mp(n,N());
		l+=s;
		
		N sm;
		assert((sm.*f)(forward<Args>(args)...));
		do {
			while (l % 2 == 0) l >>= 1;
			if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
				while (l < s) {
					l = (2 * l);
					N tmp=N::merge(sm,x[l]);
					if ((tmp.*f)(forward<Args>(args)...)) {
						sm = tmp;
						l++;
					}
				}
				return mp(l - s,sm);
			}
			sm = N::merge(sm, x[l]);
			l++;
		} while ((l & -l) != l);
		return mp(n,sm);
	}
	//UTPC2020E
	template <class F,class... Args> 
	pair<int,N> min_left(int r,F f,Args&&... args){
		assert((N().*f)(forward<Args>(args)...));
		assert(0<=r&&r<=n);
        if(r==0)return mp(0,N());
        r+=s;
        N sm;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
                while (r < s) {
                    r = (2 * r + 1);
                    N tmp=N::merge(x[r],sm);
                    if ((tmp.*f)(forward<Args>(args)...)) {
                        sm = tmp;
                        r--;
                    }
                }
                return mp(r + 1 - s,sm);
            }
            sm = N::merge(x[r], sm);
        } while ((r & -r) != r);
        return mp(0,sm);
    }
    //行列とか乗せて必要なのはベクトルとの積，みたいなときに使える？
    //CF Goodbye 2016 E
	template<class F,class T>
	T accumulate(int l, int r,F f,T t) {
		assert(0<=l&&l<=r&&r<=s);
		if (l == r) return t;

		l+=s;
		r+=s;

		static int buf[2][30];
		int cnt[2]{};
		{
			int l2 = l, r2 = r;
			while (l < r) {
				if (l & 1){
					//(x[l++].*f)(forward<Args>(args)...);
					buf[0][cnt[0]++]=l++;
				}
				if (r & 1){
					//(x[--r].*f)(forward<Args>(args)...);
					buf[1][cnt[1]++]=--r;
				}
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}
		rep(i,cnt[0])t=(x[buf[0][i]].*f)(t);
		per(i,cnt[1])t=(x[buf[1][i]].*f)(t);

		return t;
	}
};

//最も基本的な動的 segtree
//ByteCamp 2022 Day4 I
template<class N>
struct psegtree{
	struct N2{
		N v;
		int l,r;
	};
	vc<N2> x;
	int L,s;
	template<class t>
	psegtree(const vc<t>&a,int foresight=0):x(foresight){
		x.clear();
		int n=a.size();
		L=0;
		while((1<<L)<n)L++;
		s=1<<L;
		x.resize(s*2,{N(),0,0});
		rep(i,n)x[s+i].v=N(a[i]);
		gnr(i,1,s){
			x[i].v=N::merge(x[i*2].v,x[i*2+1].v);
			x[i].l=i*2;
			x[i].r=i*2+1;
		}
	}
	psegtree(int foresight=0):x(foresight){}
	int init(int n){
		x.clear();
		L=0;
		while((1<<L)<n)L++;
		s=1<<L;
		int a=nl(N());
		rep(i,L)a=nn(a,a);
		return a;
	}
	int nl(const N&val){
		x.pb({val,-1,-1});
		return si(x)-1;
	}
	int nn(int l,int r){
		x.pb({N::merge(x[l].v,x[r].v),l,r});
		return si(x)-1;
	}
	int point_set(int root,int i,const N&val){
		static int buf[40];
		rep(lv,L){
			buf[lv]=root;
			if((i>>(L-1-lv))&1)root=x[root].r;
			else root=x[root].l;
		}
		int res=nl(val);
		per(lv,L){
			int j=buf[lv];
			if((i>>(L-1-lv))&1){
				res=nn(x[j].l,res);
			}else{
				res=nn(res,x[j].r);
			}
		}
		return res;
	}
	int point_merge(int root,int i,const N&val){
		static int buf[40];
		rep(lv,L){
			buf[lv]=root;
			if((i>>(L-1-lv))&1)root=x[root].r;
			else root=x[root].l;
		}
		int res=nl(N::merge(x[root].v,val));
		per(lv,L){
			int j=buf[lv];
			if((i>>(L-1-lv))&1){
				res=nn(x[j].l,res);
			}else{
				res=nn(res,x[j].r);
			}
		}
		return res;
	}
	N compositedfs(int root,int l,int r,int b,int e){
		if(e<=l||r<=b)return N();
		if(b<=l&&r<=e)return x[root].v;
		int mid=(l+r)/2;
		return N::merge(compositedfs(x[root].l,l,mid,b,e),compositedfs(x[root].r,mid,r,b,e));
	}
	N composite(int root,int b,int e){
		assert(b<=e);
		if(b==e)return N();
		return compositedfs(root,0,s,b,e);
	}
};

struct MaxNode{
	int v;
	MaxNode(int vv=-inf):v(vv){}
	static MaxNode merge(const MaxNode&a,const MaxNode&b){
		return MaxNode(max(a.v,b.v));
	}
	bool ok(int x){return v<x;}
};

struct MinNode{
	pi v;
	MinNode(pi vv=pi(inf,-1)):v(vv){}
	static MinNode merge(const MinNode&a,const MinNode&b){
		return MinNode(min(a.v,b.v));
	}
};

struct SumNode{
	int v;
	SumNode(int vv=0):v(vv){}
	static SumNode merge(const SumNode&a,const SumNode&b){
		return SumNode(a.v+b.v);
	}
};

segtree<MinNode> minseg;
psegtree<SumNode> z(ten(5)*31*2*2+12345);
vi ls[2];

void init(int n,vi h){
	vc<pi> hi(n);
	rep(i,n)hi[i]=pi(h[i],i);
	minseg.load(hi);
	
	int root=z.init(ten(9));
	rep(phase,2){
		dmp(phase);
		segtree<MaxNode> mx(h);
		ls[phase].resize(n);
		int cur=root;
		auto add=[&](int i,int v){
			if(i<0)return;
			dmp2(i,v);
			cur=z.point_merge(cur,i,v);
		};
		vi pos;
		rep(i,n){
			dmp(i);
			while(si(pos)&&h[pos.back()]>h[i]){
				int j=gpp(pos);
				dmp2(i,j);
				int v=mx.composite(j+1,i).v;
				if(si(pos)){
					int k=pos.back();
					int w=mx.composite(k+1,j).v;
					add(w-h[j],-1);
					chmin(v,w);
				}
				add(v-h[j],1);
			}
			if(si(pos)){
				int k=pos.back();
				int w=mx.composite(k+1,i).v;
				add(w-h[i],1);
			}
			pos.pb(i);
			ls[phase][i]=cur;
		}
		reverse(all(h));
	}
	reverse(all(ls[1]));
}

int max_towers(int l,int r,int d){
	int m=minseg.composite(l,r+1).v.b;
	dmp2(l,m,r);
	int ans=0;
	ans+=z.composite(ls[0][r],d,z.s).v;
	ans-=z.composite(ls[0][m],d,z.s).v;
	dmp(ans);
	ans+=z.composite(ls[1][l],d,z.s).v;
	ans-=z.composite(ls[1][m],d,z.s).v;
	dmp(ans);
	ans++;
	dmp(ans);
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 149196 KB Output is correct
2 Correct 919 ms 151620 KB Output is correct
3 Correct 918 ms 151676 KB Output is correct
4 Correct 739 ms 151652 KB Output is correct
5 Correct 787 ms 152260 KB Output is correct
6 Correct 739 ms 151620 KB Output is correct
7 Correct 731 ms 152356 KB Output is correct
8 Correct 57 ms 146000 KB Output is correct
9 Correct 58 ms 146204 KB Output is correct
10 Correct 57 ms 146244 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 146136 KB Output is correct
2 Correct 66 ms 146224 KB Output is correct
3 Correct 59 ms 146048 KB Output is correct
4 Correct 60 ms 146124 KB Output is correct
5 Correct 60 ms 146044 KB Output is correct
6 Correct 60 ms 146248 KB Output is correct
7 Correct 62 ms 146068 KB Output is correct
8 Correct 57 ms 146120 KB Output is correct
9 Correct 58 ms 146064 KB Output is correct
10 Correct 60 ms 146080 KB Output is correct
11 Correct 65 ms 146124 KB Output is correct
12 Correct 60 ms 145992 KB Output is correct
13 Correct 67 ms 146104 KB Output is correct
14 Correct 57 ms 146052 KB Output is correct
15 Correct 62 ms 146120 KB Output is correct
16 Correct 60 ms 146128 KB Output is correct
17 Correct 60 ms 146120 KB Output is correct
18 Correct 64 ms 146248 KB Output is correct
19 Correct 58 ms 146040 KB Output is correct
20 Correct 61 ms 146068 KB Output is correct
21 Correct 59 ms 146124 KB Output is correct
22 Correct 60 ms 146120 KB Output is correct
23 Correct 58 ms 146120 KB Output is correct
24 Correct 60 ms 146096 KB Output is correct
25 Correct 59 ms 146048 KB Output is correct
26 Correct 64 ms 146132 KB Output is correct
27 Correct 71 ms 146120 KB Output is correct
28 Correct 60 ms 146052 KB Output is correct
29 Correct 61 ms 146064 KB Output is correct
30 Correct 67 ms 146120 KB Output is correct
31 Correct 60 ms 146120 KB Output is correct
32 Correct 58 ms 146120 KB Output is correct
33 Correct 59 ms 146096 KB Output is correct
34 Correct 62 ms 146252 KB Output is correct
35 Correct 59 ms 146120 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 146136 KB Output is correct
2 Correct 66 ms 146224 KB Output is correct
3 Correct 59 ms 146048 KB Output is correct
4 Correct 60 ms 146124 KB Output is correct
5 Correct 60 ms 146044 KB Output is correct
6 Correct 60 ms 146248 KB Output is correct
7 Correct 62 ms 146068 KB Output is correct
8 Correct 57 ms 146120 KB Output is correct
9 Correct 58 ms 146064 KB Output is correct
10 Correct 60 ms 146080 KB Output is correct
11 Correct 65 ms 146124 KB Output is correct
12 Correct 60 ms 145992 KB Output is correct
13 Correct 67 ms 146104 KB Output is correct
14 Correct 57 ms 146052 KB Output is correct
15 Correct 62 ms 146120 KB Output is correct
16 Correct 60 ms 146128 KB Output is correct
17 Correct 60 ms 146120 KB Output is correct
18 Correct 64 ms 146248 KB Output is correct
19 Correct 58 ms 146040 KB Output is correct
20 Correct 61 ms 146068 KB Output is correct
21 Correct 59 ms 146124 KB Output is correct
22 Correct 60 ms 146120 KB Output is correct
23 Correct 58 ms 146120 KB Output is correct
24 Correct 60 ms 146096 KB Output is correct
25 Correct 59 ms 146048 KB Output is correct
26 Correct 64 ms 146132 KB Output is correct
27 Correct 71 ms 146120 KB Output is correct
28 Correct 60 ms 146052 KB Output is correct
29 Correct 61 ms 146064 KB Output is correct
30 Correct 67 ms 146120 KB Output is correct
31 Correct 60 ms 146120 KB Output is correct
32 Correct 58 ms 146120 KB Output is correct
33 Correct 59 ms 146096 KB Output is correct
34 Correct 62 ms 146252 KB Output is correct
35 Correct 59 ms 146120 KB Output is correct
36 Correct 142 ms 149120 KB Output is correct
37 Correct 177 ms 151364 KB Output is correct
38 Correct 182 ms 151420 KB Output is correct
39 Correct 187 ms 151360 KB Output is correct
40 Correct 190 ms 151472 KB Output is correct
41 Correct 199 ms 151464 KB Output is correct
42 Correct 189 ms 151364 KB Output is correct
43 Correct 77 ms 151668 KB Output is correct
44 Correct 70 ms 152312 KB Output is correct
45 Correct 113 ms 151384 KB Output is correct
46 Correct 111 ms 151928 KB Output is correct
47 Correct 179 ms 151476 KB Output is correct
48 Correct 190 ms 151360 KB Output is correct
49 Correct 212 ms 151412 KB Output is correct
50 Correct 71 ms 152308 KB Output is correct
51 Correct 74 ms 151716 KB Output is correct
52 Correct 180 ms 151420 KB Output is correct
53 Correct 195 ms 151584 KB Output is correct
54 Correct 206 ms 151468 KB Output is correct
55 Correct 77 ms 152328 KB Output is correct
56 Correct 119 ms 151444 KB Output is correct
57 Correct 176 ms 151392 KB Output is correct
58 Correct 179 ms 151476 KB Output is correct
59 Correct 188 ms 151460 KB Output is correct
60 Correct 191 ms 151464 KB Output is correct
61 Correct 194 ms 151472 KB Output is correct
62 Correct 205 ms 151468 KB Output is correct
63 Correct 187 ms 151372 KB Output is correct
64 Correct 71 ms 151716 KB Output is correct
65 Correct 82 ms 152308 KB Output is correct
66 Correct 129 ms 151468 KB Output is correct
67 Correct 75 ms 152244 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 151436 KB Output is correct
2 Correct 786 ms 151412 KB Output is correct
3 Correct 993 ms 151408 KB Output is correct
4 Correct 954 ms 151476 KB Output is correct
5 Correct 1147 ms 151472 KB Output is correct
6 Correct 1039 ms 151368 KB Output is correct
7 Correct 971 ms 151476 KB Output is correct
8 Correct 779 ms 151728 KB Output is correct
9 Correct 777 ms 152384 KB Output is correct
10 Correct 771 ms 151680 KB Output is correct
11 Correct 783 ms 152232 KB Output is correct
12 Correct 860 ms 151656 KB Output is correct
13 Correct 795 ms 152260 KB Output is correct
14 Correct 61 ms 145988 KB Output is correct
15 Correct 60 ms 146048 KB Output is correct
16 Correct 58 ms 146144 KB Output is correct
17 Correct 195 ms 151464 KB Output is correct
18 Correct 205 ms 151476 KB Output is correct
19 Correct 206 ms 151504 KB Output is correct
20 Correct 77 ms 152260 KB Output is correct
21 Correct 73 ms 151620 KB Output is correct
22 Correct 195 ms 151464 KB Output is correct
23 Correct 197 ms 151480 KB Output is correct
24 Correct 196 ms 151420 KB Output is correct
25 Correct 71 ms 152388 KB Output is correct
26 Correct 124 ms 151432 KB Output is correct
27 Correct 64 ms 146048 KB Output is correct
28 Correct 63 ms 146132 KB Output is correct
29 Correct 61 ms 146008 KB Output is correct
30 Correct 66 ms 146092 KB Output is correct
31 Correct 59 ms 146120 KB Output is correct
32 Correct 61 ms 146124 KB Output is correct
33 Correct 60 ms 146120 KB Output is correct
34 Correct 60 ms 146120 KB Output is correct
35 Correct 59 ms 146144 KB Output is correct
36 Correct 59 ms 146120 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 147388 KB Output is correct
2 Correct 945 ms 151460 KB Output is correct
3 Correct 957 ms 151492 KB Output is correct
4 Correct 1100 ms 151364 KB Output is correct
5 Correct 992 ms 151364 KB Output is correct
6 Correct 1030 ms 151460 KB Output is correct
7 Correct 1041 ms 151500 KB Output is correct
8 Correct 738 ms 151620 KB Output is correct
9 Correct 764 ms 152336 KB Output is correct
10 Correct 868 ms 151800 KB Output is correct
11 Correct 828 ms 152264 KB Output is correct
12 Correct 180 ms 151484 KB Output is correct
13 Correct 189 ms 151448 KB Output is correct
14 Correct 197 ms 151468 KB Output is correct
15 Correct 70 ms 152272 KB Output is correct
16 Correct 122 ms 151472 KB Output is correct
17 Correct 179 ms 151396 KB Output is correct
18 Correct 176 ms 151472 KB Output is correct
19 Correct 172 ms 151444 KB Output is correct
20 Correct 190 ms 151476 KB Output is correct
21 Correct 193 ms 151364 KB Output is correct
22 Correct 200 ms 151368 KB Output is correct
23 Correct 196 ms 151460 KB Output is correct
24 Correct 71 ms 151668 KB Output is correct
25 Correct 71 ms 152328 KB Output is correct
26 Correct 125 ms 151480 KB Output is correct
27 Correct 81 ms 152240 KB Output is correct
28 Correct 59 ms 146096 KB Output is correct
29 Correct 59 ms 146120 KB Output is correct
30 Correct 60 ms 146120 KB Output is correct
31 Correct 57 ms 146056 KB Output is correct
32 Correct 58 ms 146140 KB Output is correct
33 Correct 58 ms 146060 KB Output is correct
34 Correct 59 ms 146024 KB Output is correct
35 Correct 60 ms 146028 KB Output is correct
36 Correct 60 ms 146036 KB Output is correct
37 Correct 59 ms 146092 KB Output is correct
38 Correct 59 ms 146120 KB Output is correct
39 Correct 62 ms 146120 KB Output is correct
40 Correct 58 ms 146040 KB Output is correct
41 Correct 60 ms 146124 KB Output is correct
42 Correct 58 ms 146036 KB Output is correct
43 Correct 58 ms 146024 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 146136 KB Output is correct
2 Correct 66 ms 146224 KB Output is correct
3 Correct 59 ms 146048 KB Output is correct
4 Correct 60 ms 146124 KB Output is correct
5 Correct 60 ms 146044 KB Output is correct
6 Correct 60 ms 146248 KB Output is correct
7 Correct 62 ms 146068 KB Output is correct
8 Correct 57 ms 146120 KB Output is correct
9 Correct 58 ms 146064 KB Output is correct
10 Correct 60 ms 146080 KB Output is correct
11 Correct 65 ms 146124 KB Output is correct
12 Correct 60 ms 145992 KB Output is correct
13 Correct 67 ms 146104 KB Output is correct
14 Correct 57 ms 146052 KB Output is correct
15 Correct 62 ms 146120 KB Output is correct
16 Correct 60 ms 146128 KB Output is correct
17 Correct 60 ms 146120 KB Output is correct
18 Correct 64 ms 146248 KB Output is correct
19 Correct 58 ms 146040 KB Output is correct
20 Correct 61 ms 146068 KB Output is correct
21 Correct 59 ms 146124 KB Output is correct
22 Correct 60 ms 146120 KB Output is correct
23 Correct 58 ms 146120 KB Output is correct
24 Correct 60 ms 146096 KB Output is correct
25 Correct 59 ms 146048 KB Output is correct
26 Correct 64 ms 146132 KB Output is correct
27 Correct 71 ms 146120 KB Output is correct
28 Correct 60 ms 146052 KB Output is correct
29 Correct 61 ms 146064 KB Output is correct
30 Correct 67 ms 146120 KB Output is correct
31 Correct 60 ms 146120 KB Output is correct
32 Correct 58 ms 146120 KB Output is correct
33 Correct 59 ms 146096 KB Output is correct
34 Correct 62 ms 146252 KB Output is correct
35 Correct 59 ms 146120 KB Output is correct
36 Correct 142 ms 149120 KB Output is correct
37 Correct 177 ms 151364 KB Output is correct
38 Correct 182 ms 151420 KB Output is correct
39 Correct 187 ms 151360 KB Output is correct
40 Correct 190 ms 151472 KB Output is correct
41 Correct 199 ms 151464 KB Output is correct
42 Correct 189 ms 151364 KB Output is correct
43 Correct 77 ms 151668 KB Output is correct
44 Correct 70 ms 152312 KB Output is correct
45 Correct 113 ms 151384 KB Output is correct
46 Correct 111 ms 151928 KB Output is correct
47 Correct 179 ms 151476 KB Output is correct
48 Correct 190 ms 151360 KB Output is correct
49 Correct 212 ms 151412 KB Output is correct
50 Correct 71 ms 152308 KB Output is correct
51 Correct 74 ms 151716 KB Output is correct
52 Correct 180 ms 151420 KB Output is correct
53 Correct 195 ms 151584 KB Output is correct
54 Correct 206 ms 151468 KB Output is correct
55 Correct 77 ms 152328 KB Output is correct
56 Correct 119 ms 151444 KB Output is correct
57 Correct 176 ms 151392 KB Output is correct
58 Correct 179 ms 151476 KB Output is correct
59 Correct 188 ms 151460 KB Output is correct
60 Correct 191 ms 151464 KB Output is correct
61 Correct 194 ms 151472 KB Output is correct
62 Correct 205 ms 151468 KB Output is correct
63 Correct 187 ms 151372 KB Output is correct
64 Correct 71 ms 151716 KB Output is correct
65 Correct 82 ms 152308 KB Output is correct
66 Correct 129 ms 151468 KB Output is correct
67 Correct 75 ms 152244 KB Output is correct
68 Correct 796 ms 151436 KB Output is correct
69 Correct 786 ms 151412 KB Output is correct
70 Correct 993 ms 151408 KB Output is correct
71 Correct 954 ms 151476 KB Output is correct
72 Correct 1147 ms 151472 KB Output is correct
73 Correct 1039 ms 151368 KB Output is correct
74 Correct 971 ms 151476 KB Output is correct
75 Correct 779 ms 151728 KB Output is correct
76 Correct 777 ms 152384 KB Output is correct
77 Correct 771 ms 151680 KB Output is correct
78 Correct 783 ms 152232 KB Output is correct
79 Correct 860 ms 151656 KB Output is correct
80 Correct 795 ms 152260 KB Output is correct
81 Correct 61 ms 145988 KB Output is correct
82 Correct 60 ms 146048 KB Output is correct
83 Correct 58 ms 146144 KB Output is correct
84 Correct 195 ms 151464 KB Output is correct
85 Correct 205 ms 151476 KB Output is correct
86 Correct 206 ms 151504 KB Output is correct
87 Correct 77 ms 152260 KB Output is correct
88 Correct 73 ms 151620 KB Output is correct
89 Correct 195 ms 151464 KB Output is correct
90 Correct 197 ms 151480 KB Output is correct
91 Correct 196 ms 151420 KB Output is correct
92 Correct 71 ms 152388 KB Output is correct
93 Correct 124 ms 151432 KB Output is correct
94 Correct 64 ms 146048 KB Output is correct
95 Correct 63 ms 146132 KB Output is correct
96 Correct 61 ms 146008 KB Output is correct
97 Correct 66 ms 146092 KB Output is correct
98 Correct 59 ms 146120 KB Output is correct
99 Correct 61 ms 146124 KB Output is correct
100 Correct 60 ms 146120 KB Output is correct
101 Correct 60 ms 146120 KB Output is correct
102 Correct 59 ms 146144 KB Output is correct
103 Correct 59 ms 146120 KB Output is correct
104 Correct 865 ms 151108 KB Output is correct
105 Correct 1139 ms 151364 KB Output is correct
106 Correct 998 ms 151468 KB Output is correct
107 Correct 1030 ms 151472 KB Output is correct
108 Correct 1024 ms 151468 KB Output is correct
109 Correct 1149 ms 151344 KB Output is correct
110 Correct 1082 ms 151364 KB Output is correct
111 Correct 835 ms 151732 KB Output is correct
112 Correct 851 ms 152324 KB Output is correct
113 Correct 827 ms 151392 KB Output is correct
114 Correct 922 ms 152348 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 149196 KB Output is correct
2 Correct 919 ms 151620 KB Output is correct
3 Correct 918 ms 151676 KB Output is correct
4 Correct 739 ms 151652 KB Output is correct
5 Correct 787 ms 152260 KB Output is correct
6 Correct 739 ms 151620 KB Output is correct
7 Correct 731 ms 152356 KB Output is correct
8 Correct 57 ms 146000 KB Output is correct
9 Correct 58 ms 146204 KB Output is correct
10 Correct 57 ms 146244 KB Output is correct
11 Correct 59 ms 146136 KB Output is correct
12 Correct 66 ms 146224 KB Output is correct
13 Correct 59 ms 146048 KB Output is correct
14 Correct 60 ms 146124 KB Output is correct
15 Correct 60 ms 146044 KB Output is correct
16 Correct 60 ms 146248 KB Output is correct
17 Correct 62 ms 146068 KB Output is correct
18 Correct 57 ms 146120 KB Output is correct
19 Correct 58 ms 146064 KB Output is correct
20 Correct 60 ms 146080 KB Output is correct
21 Correct 65 ms 146124 KB Output is correct
22 Correct 60 ms 145992 KB Output is correct
23 Correct 67 ms 146104 KB Output is correct
24 Correct 57 ms 146052 KB Output is correct
25 Correct 62 ms 146120 KB Output is correct
26 Correct 60 ms 146128 KB Output is correct
27 Correct 60 ms 146120 KB Output is correct
28 Correct 64 ms 146248 KB Output is correct
29 Correct 58 ms 146040 KB Output is correct
30 Correct 61 ms 146068 KB Output is correct
31 Correct 59 ms 146124 KB Output is correct
32 Correct 60 ms 146120 KB Output is correct
33 Correct 58 ms 146120 KB Output is correct
34 Correct 60 ms 146096 KB Output is correct
35 Correct 59 ms 146048 KB Output is correct
36 Correct 64 ms 146132 KB Output is correct
37 Correct 71 ms 146120 KB Output is correct
38 Correct 60 ms 146052 KB Output is correct
39 Correct 61 ms 146064 KB Output is correct
40 Correct 67 ms 146120 KB Output is correct
41 Correct 60 ms 146120 KB Output is correct
42 Correct 58 ms 146120 KB Output is correct
43 Correct 59 ms 146096 KB Output is correct
44 Correct 62 ms 146252 KB Output is correct
45 Correct 59 ms 146120 KB Output is correct
46 Correct 142 ms 149120 KB Output is correct
47 Correct 177 ms 151364 KB Output is correct
48 Correct 182 ms 151420 KB Output is correct
49 Correct 187 ms 151360 KB Output is correct
50 Correct 190 ms 151472 KB Output is correct
51 Correct 199 ms 151464 KB Output is correct
52 Correct 189 ms 151364 KB Output is correct
53 Correct 77 ms 151668 KB Output is correct
54 Correct 70 ms 152312 KB Output is correct
55 Correct 113 ms 151384 KB Output is correct
56 Correct 111 ms 151928 KB Output is correct
57 Correct 179 ms 151476 KB Output is correct
58 Correct 190 ms 151360 KB Output is correct
59 Correct 212 ms 151412 KB Output is correct
60 Correct 71 ms 152308 KB Output is correct
61 Correct 74 ms 151716 KB Output is correct
62 Correct 180 ms 151420 KB Output is correct
63 Correct 195 ms 151584 KB Output is correct
64 Correct 206 ms 151468 KB Output is correct
65 Correct 77 ms 152328 KB Output is correct
66 Correct 119 ms 151444 KB Output is correct
67 Correct 176 ms 151392 KB Output is correct
68 Correct 179 ms 151476 KB Output is correct
69 Correct 188 ms 151460 KB Output is correct
70 Correct 191 ms 151464 KB Output is correct
71 Correct 194 ms 151472 KB Output is correct
72 Correct 205 ms 151468 KB Output is correct
73 Correct 187 ms 151372 KB Output is correct
74 Correct 71 ms 151716 KB Output is correct
75 Correct 82 ms 152308 KB Output is correct
76 Correct 129 ms 151468 KB Output is correct
77 Correct 75 ms 152244 KB Output is correct
78 Correct 796 ms 151436 KB Output is correct
79 Correct 786 ms 151412 KB Output is correct
80 Correct 993 ms 151408 KB Output is correct
81 Correct 954 ms 151476 KB Output is correct
82 Correct 1147 ms 151472 KB Output is correct
83 Correct 1039 ms 151368 KB Output is correct
84 Correct 971 ms 151476 KB Output is correct
85 Correct 779 ms 151728 KB Output is correct
86 Correct 777 ms 152384 KB Output is correct
87 Correct 771 ms 151680 KB Output is correct
88 Correct 783 ms 152232 KB Output is correct
89 Correct 860 ms 151656 KB Output is correct
90 Correct 795 ms 152260 KB Output is correct
91 Correct 61 ms 145988 KB Output is correct
92 Correct 60 ms 146048 KB Output is correct
93 Correct 58 ms 146144 KB Output is correct
94 Correct 195 ms 151464 KB Output is correct
95 Correct 205 ms 151476 KB Output is correct
96 Correct 206 ms 151504 KB Output is correct
97 Correct 77 ms 152260 KB Output is correct
98 Correct 73 ms 151620 KB Output is correct
99 Correct 195 ms 151464 KB Output is correct
100 Correct 197 ms 151480 KB Output is correct
101 Correct 196 ms 151420 KB Output is correct
102 Correct 71 ms 152388 KB Output is correct
103 Correct 124 ms 151432 KB Output is correct
104 Correct 64 ms 146048 KB Output is correct
105 Correct 63 ms 146132 KB Output is correct
106 Correct 61 ms 146008 KB Output is correct
107 Correct 66 ms 146092 KB Output is correct
108 Correct 59 ms 146120 KB Output is correct
109 Correct 61 ms 146124 KB Output is correct
110 Correct 60 ms 146120 KB Output is correct
111 Correct 60 ms 146120 KB Output is correct
112 Correct 59 ms 146144 KB Output is correct
113 Correct 59 ms 146120 KB Output is correct
114 Correct 334 ms 147388 KB Output is correct
115 Correct 945 ms 151460 KB Output is correct
116 Correct 957 ms 151492 KB Output is correct
117 Correct 1100 ms 151364 KB Output is correct
118 Correct 992 ms 151364 KB Output is correct
119 Correct 1030 ms 151460 KB Output is correct
120 Correct 1041 ms 151500 KB Output is correct
121 Correct 738 ms 151620 KB Output is correct
122 Correct 764 ms 152336 KB Output is correct
123 Correct 868 ms 151800 KB Output is correct
124 Correct 828 ms 152264 KB Output is correct
125 Correct 180 ms 151484 KB Output is correct
126 Correct 189 ms 151448 KB Output is correct
127 Correct 197 ms 151468 KB Output is correct
128 Correct 70 ms 152272 KB Output is correct
129 Correct 122 ms 151472 KB Output is correct
130 Correct 179 ms 151396 KB Output is correct
131 Correct 176 ms 151472 KB Output is correct
132 Correct 172 ms 151444 KB Output is correct
133 Correct 190 ms 151476 KB Output is correct
134 Correct 193 ms 151364 KB Output is correct
135 Correct 200 ms 151368 KB Output is correct
136 Correct 196 ms 151460 KB Output is correct
137 Correct 71 ms 151668 KB Output is correct
138 Correct 71 ms 152328 KB Output is correct
139 Correct 125 ms 151480 KB Output is correct
140 Correct 81 ms 152240 KB Output is correct
141 Correct 59 ms 146096 KB Output is correct
142 Correct 59 ms 146120 KB Output is correct
143 Correct 60 ms 146120 KB Output is correct
144 Correct 57 ms 146056 KB Output is correct
145 Correct 58 ms 146140 KB Output is correct
146 Correct 58 ms 146060 KB Output is correct
147 Correct 59 ms 146024 KB Output is correct
148 Correct 60 ms 146028 KB Output is correct
149 Correct 60 ms 146036 KB Output is correct
150 Correct 59 ms 146092 KB Output is correct
151 Correct 59 ms 146120 KB Output is correct
152 Correct 62 ms 146120 KB Output is correct
153 Correct 58 ms 146040 KB Output is correct
154 Correct 60 ms 146124 KB Output is correct
155 Correct 58 ms 146036 KB Output is correct
156 Correct 58 ms 146024 KB Output is correct
157 Correct 865 ms 151108 KB Output is correct
158 Correct 1139 ms 151364 KB Output is correct
159 Correct 998 ms 151468 KB Output is correct
160 Correct 1030 ms 151472 KB Output is correct
161 Correct 1024 ms 151468 KB Output is correct
162 Correct 1149 ms 151344 KB Output is correct
163 Correct 1082 ms 151364 KB Output is correct
164 Correct 835 ms 151732 KB Output is correct
165 Correct 851 ms 152324 KB Output is correct
166 Correct 827 ms 151392 KB Output is correct
167 Correct 922 ms 152348 KB Output is correct
168 Correct 65 ms 145992 KB Output is correct
169 Correct 746 ms 148320 KB Output is correct
170 Correct 1509 ms 151472 KB Output is correct
171 Correct 1527 ms 151360 KB Output is correct
172 Correct 1573 ms 151364 KB Output is correct
173 Correct 1486 ms 151364 KB Output is correct
174 Correct 1241 ms 151416 KB Output is correct
175 Correct 1347 ms 151492 KB Output is correct
176 Correct 813 ms 151692 KB Output is correct
177 Correct 782 ms 152344 KB Output is correct
178 Correct 1070 ms 151604 KB Output is correct
179 Correct 964 ms 151848 KB Output is correct