oj.uz

답안 #313779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313779 2020-10-17T04:39:07 Z AngelKnows Sky Walking (IOI19_walk) C++14
100 / 100
 1299 ms 58488 KB 
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair

typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=100000+10;
const double eps=1e-5;
const int mo=1e9+7;

int n,m,m2;
ll x[N],h[N];
struct bridge {
	int l,r;
	ll y;
} e[N];
bool cmp(bridge a,bridge b) {
	if (a.y==b.y&&a.l!=b.l) return a.l<b.l;
	if (a.y==b.y&&a.l==b.l) return a.r<b.r;
	return a.y<b.y;
}
bool cmp2(int a,int b) {
	if (e[a].y==e[b].y&&e[a].l!=e[b].l) return e[a].l<e[b].l;
	if (e[a].y==e[b].y&&e[a].r!=e[b].r) return e[a].r<e[b].r;
	return e[a].y>e[b].y;
}
int s,g;
vector<int> c,d;
int ch,ct,dh,dt;
vector<int> lb[N],rb[N];
ll rec[N];
int to[N];
ll slt[3][4*N],srt[3][4*N],glt[3][4*N],grt[3][4*N];
struct state {
	int maxh,l,r,lstop,rstop;
} su,gu;
bool turn;// 0表示轮到sr向右移动，1表示轮到gr向右移动 
int slp[4*N],srp[4*N],glp[4*N],grp[4*N];
stack<int> b;
vector<int> lbu[N],rbu[N];
ll backup[N];
ll ans=linf;
void modify2(int tree[],int p,int l,int r,int x,int v) {
	if (l>r) return;
	if (x<l||x>r) return;
	if (l==r) {
		tree[p]=v;
		return;
	}
	int mid=(l+r)/2;
	if (x<=mid) modify2(tree,2*p,l,mid,x,v);
	else modify2(tree,2*p+1,mid+1,r,x,v);
	tree[p]=max(tree[2*p],tree[2*p+1]);
}
int query2(int tree[],int p,int l,int r,int L,int R) {
	if (l>r||L>R) return 0;
	if (L<l||R>r) return 0;
	if (l==L&&r==R) return tree[p];
	int mid=(l+r)/2;
	if (R<=mid) return query2(tree,2*p,l,mid,L,R);
	else if (L>mid) return query2(tree,2*p+1,mid+1,r,L,R);
	else return max(query2(tree,2*p,l,mid,L,mid),query2(tree,2*p+1,mid+1,r,mid+1,R));
}
ll query(ll tree[],int p,int l,int r,int L,int R) {
	if (l>r||L>R) return 0;
	if (L<l||R>r) return 0;
	if (l==L&&r==R) return tree[p];
	int mid=(l+r)/2;
	if (R<=mid) return query(tree,2*p,l,mid,L,R);
	else if (L>mid) return query(tree,2*p+1,mid+1,r,L,R);
	else return min(query(tree,2*p,l,mid,L,mid),query(tree,2*p+1,mid+1,r,mid+1,R));
}
void modify(ll tree[],int p,int l,int r,int x,ll v) {
	if (l>r) return;
	if (x<l||x>r) return;
	if (l==r) {
		tree[p]=v;
		return;
	}
	int mid=(l+r)/2;
	if (x<=mid) modify(tree,2*p,l,mid,x,v);
	else modify(tree,2*p+1,mid+1,r,x,v);
	tree[p]=min(tree[2*p],tree[2*p+1]);
}
void update(ll tree[][4*N],int p,int l,int r,int x,ll v) {
	modify(tree[0],p,l,r,x,v);
	if (v!=linf) modify(tree[1],p,l,r,x,v+rec[x]);
	else modify(tree[1],p,l,r,x,linf);
	if (v!=linf) modify(tree[2],p,l,r,x,v-rec[x]);
	else modify(tree[2],p,l,r,x,linf);
}
void del(ll tree[][4*N],int p,int l,int r,int x) {
	update(tree,p,l,r,x,linf);
}
int find(ll h) {
	int l=1,r=m2;
	int mid,ok=0;
	while (l<=r) {
		mid=(l+r)/2;
		if (rec[mid]<=h) {
			ok=mid;
			l=mid+1;
		} else r=mid-1;
	}
	return ok;
}
int find2(int tree[],ll h) {
	int x=find(h);
	if (x==0) return 0;
	return query2(tree,1,1,m2,1,x);
}
ll add(ll x,ll y) {
	if (x==linf||y==linf) return linf;
	return x+y;
}
void compute(int x,int o) {
	int sl=0,sr=0,gl=0,gr=0;
	if (o==0) {
		sl=x;
		for (auto &it:lbu[sl]) {
			int x=find2(slp,h[it]);
			int t=find2(slp,h[sl]);
			if (x&&t&&x<=t) {
				ll v=query(slt[0],1,1,m2,x,x);
				ll v2=add(query(slt[1],1,1,m2,x,t),-rec[x]);
				if (v2<v) update(slt,1,1,m2,x,v2);
			}
		}
		for (auto &it:lb[sl]) {
			modify2(slp,1,1,m2,to[it],to[it]);
			ll v=query(slt[0],1,1,m2,to[it],to[it]);
			int x=find2(slp,h[sl]);
			ll v2=linf;
			if (x) v2=add(query(slt[1],1,1,m2,to[it],x),-rec[to[it]]);
			ll v3=add(query(slt[2],1,1,m2,1,to[it]),rec[to[it]]);
			ll v4=min(v,min(v2,v3));
			backup[to[it]]=v4;
		}
		if (sl!=1) for (auto &it:rb[sl]) {
			int x=find2(slp,rec[to[it]]-1);
			if (x) {
				ll v=query(slt[0],1,1,m2,x,x);
				ll v2=add(query(slt[1],1,1,m2,to[it],to[it]),-rec[x]);
				if (v2<v) update(slt,1,1,m2,x,v2);
			}
			modify2(slp,1,1,m2,to[it],0);
			del(slt,1,1,m2,to[it]);
		}
		for (auto &it:lb[sl]) {
			modify2(slp,1,1,m2,to[it],to[it]);
			ll v4=backup[to[it]];
			if (v4!=linf) update(slt,1,1,m2,to[it],v4);
		}
	} else if (o==1) {
		sr=x;
		for (auto &it:rbu[sr]) {
			int x=find2(srp,h[it]);
			int t=find2(srp,h[sr]);
			if (x&&t&&x<=t) {
				ll v=query(srt[0],1,1,m2,x,x);
				ll v2=add(query(srt[1],1,1,m2,x,t),-rec[x]);
				if (v2<v) update(srt,1,1,m2,x,v2);
			}
		}
		for (auto &it:rb[sr]) {
			modify2(srp,1,1,m2,to[it],to[it]);
			ll v=query(srt[0],1,1,m2,to[it],to[it]);
			int x=find2(srp,h[sr]);
			ll v2=linf;
			if (x) v2=add(query(srt[1],1,1,m2,to[it],x),-rec[to[it]]);
			ll v3=add(query(srt[2],1,1,m2,1,to[it]),rec[to[it]]);
			ll v4=min(v,min(v2,v3));
			backup[to[it]]=v4;
		}
		if (sr!=n) for (auto &it:lb[sr]) {
			int x=find2(srp,rec[to[it]]-1);
			if (x) {
				ll v=query(srt[0],1,1,m2,x,x);
				ll v2=add(query(srt[1],1,1,m2,to[it],to[it]),-rec[x]);
				if (v2<v) update(srt,1,1,m2,x,v2);
			}
			modify2(srp,1,1,m2,to[it],0);
			del(srt,1,1,m2,to[it]);
		}
		for (auto &it:rb[sr]) {
			modify2(srp,1,1,m2,to[it],to[it]);
			ll v4=backup[to[it]];
			if (v4!=linf) update(srt,1,1,m2,to[it],v4);
		}
	} else if (o==2) {
		gl=x;
		for (auto &it:lbu[gl]) {
			int x=find2(glp,h[it]);
			int t=find2(glp,h[gl]);
			if (x&&t&&x<=t) {
				ll v=query(glt[0],1,1,m2,x,x);
				ll v2=add(query(glt[1],1,1,m2,x,t),-rec[x]);
				if (v2<v) update(glt,1,1,m2,x,v2);
			}
		}
		for (auto &it:lb[gl]) {
			modify2(glp,1,1,m2,to[it],to[it]);
			ll v=query(glt[0],1,1,m2,to[it],to[it]);
			int x=find2(glp,h[gl]);
			ll v2=linf;
			if (x) v2=add(query(glt[1],1,1,m2,to[it],x),-rec[to[it]]);
			ll v3=add(query(glt[2],1,1,m2,1,to[it]),rec[to[it]]);
			ll v4=min(v,min(v2,v3));
			backup[to[it]]=v4;
		}
		if (gl!=1) for (auto &it:rb[gl]) {
			int x=find2(glp,rec[to[it]]-1);
			if (x) {
				ll v=query(glt[0],1,1,m2,x,x);
				ll v2=add(query(glt[1],1,1,m2,to[it],to[it]),-rec[x]);
				if (v2<v) update(glt,1,1,m2,x,v2);
			}
			modify2(glp,1,1,m2,to[it],0);
			del(glt,1,1,m2,to[it]);
		}
		for (auto &it:lb[gl]) {
			modify2(glp,1,1,m2,to[it],to[it]);
			ll v4=backup[to[it]];
			if (v4!=linf) update(glt,1,1,m2,to[it],v4);
		}
	} else if (o==3) {
		gr=x;
		for (auto &it:rbu[gr]) {
			int x=find2(grp,h[it]);
			int t=find2(grp,h[gr]);
			if (x&&t&&x<=t) {
				ll v=query(grt[0],1,1,m2,x,x);
				ll v2=add(query(grt[1],1,1,m2,x,t),-rec[x]);
				if (v2<v) update(grt,1,1,m2,x,v2);
			}
		}
		for (auto &it:rb[gr]) {
			modify2(grp,1,1,m2,to[it],to[it]);
			ll v=query(grt[0],1,1,m2,to[it],to[it]);
			int x=find2(grp,h[gr]);
			ll v2=linf;
			if (x) v2=add(query(grt[1],1,1,m2,to[it],x),-rec[to[it]]);
			ll v3=add(query(grt[2],1,1,m2,1,to[it]),rec[to[it]]);
			ll v4=min(v,min(v2,v3));
			backup[to[it]]=v4;
		}
		if (gr!=n) for (auto &it:lb[gr]) {
			int x=find2(grp,rec[to[it]]-1);
			if (x) {
				ll v=query(grt[0],1,1,m2,x,x);
				ll v2=add(query(grt[1],1,1,m2,to[it],to[it]),-rec[x]);
				if (v2<v) update(grt,1,1,m2,x,v2);
			}
			modify2(grp,1,1,m2,to[it],0);
			del(grt,1,1,m2,to[it]);
		}
		for (auto &it:rb[gr]) {
			modify2(grp,1,1,m2,to[it],to[it]);
			ll v4=backup[to[it]];
			if (v4!=linf) update(grt,1,1,m2,to[it],v4);
		}
	}
}
long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int ss, int gg) {
	s=ss+1;
	g=gg+1;
	n=X.size(),m=Y.size();
	FOR(i,n) x[i]=X[i-1],h[i]=H[i-1];
	FOR(i,m) e[i].l=L[i-1]+1,e[i].r=R[i-1]+1,e[i].y=Y[i-1];
	sort(e+1,e+1+m,cmp);
	if (s>g) swap(s,g);
    // 离散化 
    FOR(i,m) {
    	if (i==1||e[i].y!=e[i-1].y) rec[++m2]=e[i].y;
		to[i]=m2;
	}
	// 建筑的左右天桥 
    FOR(i,m) {
    	lb[e[i].r].pb(i);
    	rb[e[i].l].pb(i);
	}
	// 从高到低排序以便弹出天桥的时候自上而下继承更新 
	FOR(i,n) sort(lb[i].begin(),lb[i].end(),cmp2);
	FOR(i,n) sort(rb[i].begin(),rb[i].end(),cmp2);
	// 跨越s横坐标的天桥
    FOR(i,m) if (e[i].l<=s&&e[i].r>=s) c.pb(i);
    FOR(i,m) if (e[i].l<=g&&e[i].r>=g) d.pb(i);
    ch=0,ct=(int)c.size()-1,dh=0,dt=(int)d.size()-1;
    // 预处理从建筑i能看到的所有建筑j（从左或者从右） 
	REP(i,s,n) {
		while (!b.empty()&&h[b.top()]<h[i]) b.pop();
		if (!b.empty()) {
			int x=b.top();
			rbu[x].pb(i);
		}
		b.push(i);
	}
	while (!b.empty()) b.pop();
	for (int i=s;i>=1;i--) {
		while (!b.empty()&&h[b.top()]<h[i]) b.pop();
		if (!b.empty()) {
			int x=b.top();
			lbu[x].pb(i);
		}
		b.push(i);
	}
	while (!b.empty()) b.pop();
	// 初始化停留在s,g的扫描线
    FOR(i,m2) {
    	del(slt,1,1,m2,i);
    	del(srt,1,1,m2,i);
	}
	FOR(i,m2) {
    	del(glt,1,1,m2,i);
    	del(grt,1,1,m2,i);
	}
	while (ch<=ct&&e[c[ch]].y<=h[s]) {
		int u=to[c[ch]];
		update(slt,1,1,m2,u,e[c[ch]].y);
		update(srt,1,1,m2,u,e[c[ch]].y);
		modify2(slp,1,1,m2,u,u);
		modify2(srp,1,1,m2,u,u);
		ch++;
	}
	while (dh<=dt&&e[d[dh]].y<=h[g]) {
		int u=to[d[dh]];
		update(glt,1,1,m2,u,e[d[dh]].y);
		update(grt,1,1,m2,u,e[d[dh]].y);
		modify2(glp,1,1,m2,u,u);
		modify2(grp,1,1,m2,u,u);
		dh++;
	}
	// 扩展扫描矩形
	su.l=s,su.r=s,gu.l=g,gu.r=g;
	su.maxh=h[s],gu.maxh=h[g];
    while (1) {
    	if (turn==0) {
    		if (su.r==n) break;
    		compute(su.r,1); // 把之前的扫描线更新为新的扫描线作准备 
			su.r++;
			if (su.r>=g) turn=1;
			while (h[su.r]>su.maxh) {
				while (su.l>=1) {
					if (h[su.l]>su.maxh) {
						su.maxh=min(h[su.l],h[su.r]);
						while (ch<=ct&&e[c[ch]].y<=su.maxh) {
							int u=to[c[ch]];
							ll vl=add(query(slt[2],1,1,m2,1,u),e[c[ch]].y+x[s]-x[su.l]);
							ll vr=add(query(srt[2],1,1,m2,1,u),e[c[ch]].y+x[su.r]-x[s]);
							modify2(slp,1,1,m2,u,u);
							modify2(srp,1,1,m2,u,u);
							if (vl!=linf) update(slt,1,1,m2,u,vl-(x[s]-x[su.l]));
							if (vr!=linf) update(srt,1,1,m2,u,vr-(x[su.r]-x[s]));
							if (vl!=linf&&vl+x[su.r]-x[su.l]<vr) update(srt,1,1,m2,u,vl+x[su.r]-x[su.l]-(x[su.r]-x[s]));
							else if (vr!=linf&&vr+x[su.r]-x[su.l]<vl) update(slt,1,1,m2,u,vr+x[su.r]-x[su.l]-(x[s]-x[su.l]));
							ch++;
						}
						break;
					} else {
						compute(su.l,0);
						if (su.l>1) su.l--;
						else {
							su.maxh=h[su.r];
							break;
						}
					}
				}
			}
			
		} else {
			ll v1,v2;
			v1=v2=linf;
			int j=find2(srp,h[su.r]),k;
			if (j) {
				v1=add(query(srt[1],1,1,m2,1,j),x[su.r]-x[s]);
				k=find2(grp,min(rec[j],h[gu.r]));
			}
			if (k) v2=add(query(grt[2],1,1,m2,1,k),x[gu.r]-x[g]);
			ans=min(ans,add(v1,v2));
			
			if (gu.r==n) break;
			compute(gu.r,3);
			gu.r++;
			turn=0;
			while (h[gu.r]>gu.maxh) {
				while (gu.l>=1) {
					if (h[gu.l]>gu.maxh) {
						gu.maxh=min(h[gu.l],h[gu.r]);
						while (dh<=dt&&e[d[dh]].y<=gu.maxh) {
							int u=to[d[dh]];
							ll vl=add(query(glt[2],1,1,m2,1,u),e[d[dh]].y+x[g]-x[gu.l]);
							ll vr=add(query(grt[2],1,1,m2,1,u),e[d[dh]].y+x[gu.r]-x[g]);
							modify2(glp,1,1,m2,u,u);
							modify2(grp,1,1,m2,u,u);
							if (vl!=linf) update(glt,1,1,m2,u,vl-(x[g]-x[gu.l]));
							if (vr!=linf) update(grt,1,1,m2,u,vr-(x[gu.r]-x[g]));
							if (vl!=linf&&vl+x[gu.r]-x[gu.l]<vr) update(grt,1,1,m2,u,vl+x[gu.r]-x[gu.l]-(x[gu.r]-x[g]));
							else if (vr!=linf&&vr+x[gu.r]-x[gu.l]<vl) update(glt,1,1,m2,u,vr+x[gu.r]-x[gu.l]-(x[g]-x[gu.l]));
							dh++;
						}
						break;
					} else {
						compute(gu.l,2);
						if (gu.l>1) gu.l--;
						else {
							gu.maxh=h[gu.r];
							break;
						}
					}
				}
			}
		}
	}
	if (ans==linf) ans=-1;
	return ans;
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:389:17: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  389 |    if (k) v2=add(query(grt[2],1,1,m2,1,k),x[gu.r]-x[g]);
      |              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 7 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 7 ms 9856 KB Output is correct
11 Correct 7 ms 9856 KB Output is correct
12 Correct 7 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 8 ms 9856 KB Output is correct
15 Correct 7 ms 9856 KB Output is correct
16 Correct 7 ms 9856 KB Output is correct
17 Correct 7 ms 9856 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 8 ms 9856 KB Output is correct
3 Correct 690 ms 48516 KB Output is correct
4 Correct 1006 ms 58488 KB Output is correct
5 Correct 858 ms 54136 KB Output is correct
6 Correct 853 ms 54392 KB Output is correct
7 Correct 846 ms 53376 KB Output is correct
8 Correct 1091 ms 48632 KB Output is correct
9 Correct 1200 ms 55460 KB Output is correct
10 Correct 1188 ms 57208 KB Output is correct
11 Correct 954 ms 51704 KB Output is correct
12 Correct 814 ms 56700 KB Output is correct
13 Correct 825 ms 56824 KB Output is correct
14 Correct 842 ms 55668 KB Output is correct
15 Correct 519 ms 34040 KB Output is correct
16 Correct 407 ms 29048 KB Output is correct
17 Correct 301 ms 27340 KB Output is correct
18 Correct 605 ms 55532 KB Output is correct
19 Correct 29 ms 12288 KB Output is correct
20 Correct 271 ms 30964 KB Output is correct
21 Correct 125 ms 25848 KB Output is correct
22 Correct 137 ms 30072 KB Output is correct
23 Correct 433 ms 43508 KB Output is correct
24 Correct 259 ms 30072 KB Output is correct
25 Correct 152 ms 26560 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 14072 KB Output is correct
2 Correct 673 ms 45816 KB Output is correct
3 Correct 687 ms 45504 KB Output is correct
4 Correct 792 ms 52860 KB Output is correct
5 Correct 768 ms 51736 KB Output is correct
6 Correct 776 ms 54596 KB Output is correct
7 Correct 379 ms 36260 KB Output is correct
8 Correct 741 ms 55032 KB Output is correct
9 Correct 745 ms 55796 KB Output is correct
10 Correct 376 ms 39216 KB Output is correct
11 Correct 28 ms 13688 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 14072 KB Output is correct
2 Correct 673 ms 45816 KB Output is correct
3 Correct 687 ms 45504 KB Output is correct
4 Correct 792 ms 52860 KB Output is correct
5 Correct 768 ms 51736 KB Output is correct
6 Correct 776 ms 54596 KB Output is correct
7 Correct 379 ms 36260 KB Output is correct
8 Correct 741 ms 55032 KB Output is correct
9 Correct 745 ms 55796 KB Output is correct
10 Correct 376 ms 39216 KB Output is correct
11 Correct 28 ms 13688 KB Output is correct
12 Correct 721 ms 45304 KB Output is correct
13 Correct 823 ms 51132 KB Output is correct
14 Correct 876 ms 49656 KB Output is correct
15 Correct 400 ms 37112 KB Output is correct
16 Correct 491 ms 36088 KB Output is correct
17 Correct 499 ms 36216 KB Output is correct
18 Correct 395 ms 36984 KB Output is correct
19 Correct 491 ms 36088 KB Output is correct
20 Correct 462 ms 34680 KB Output is correct
21 Correct 94 ms 15480 KB Output is correct
22 Correct 509 ms 48632 KB Output is correct
23 Correct 514 ms 49016 KB Output is correct
24 Correct 524 ms 49400 KB Output is correct
25 Correct 562 ms 49016 KB Output is correct
26 Correct 511 ms 49784 KB Output is correct
27 Correct 835 ms 50796 KB Output is correct
28 Correct 794 ms 50888 KB Output is correct
29 Correct 876 ms 52056 KB Output is correct
30 Correct 454 ms 34424 KB Output is correct
31 Correct 861 ms 53932 KB Output is correct
32 Correct 330 ms 31224 KB Output is correct
33 Correct 337 ms 33144 KB Output is correct
34 Correct 392 ms 42616 KB Output is correct
35 Correct 379 ms 34808 KB Output is correct
36 Correct 349 ms 33912 KB Output is correct
37 Correct 124 ms 25720 KB Output is correct
38 Correct 135 ms 30072 KB Output is correct
39 Correct 431 ms 43616 KB Output is correct
40 Correct 264 ms 30140 KB Output is correct
41 Correct 154 ms 26572 KB Output is correct

Subtask #5
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9856 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 7 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 7 ms 9856 KB Output is correct
11 Correct 7 ms 9856 KB Output is correct
12 Correct 7 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 8 ms 9856 KB Output is correct
15 Correct 7 ms 9856 KB Output is correct
16 Correct 7 ms 9856 KB Output is correct
17 Correct 7 ms 9856 KB Output is correct
18 Correct 7 ms 9856 KB Output is correct
19 Correct 8 ms 9856 KB Output is correct
20 Correct 690 ms 48516 KB Output is correct
21 Correct 1006 ms 58488 KB Output is correct
22 Correct 858 ms 54136 KB Output is correct
23 Correct 853 ms 54392 KB Output is correct
24 Correct 846 ms 53376 KB Output is correct
25 Correct 1091 ms 48632 KB Output is correct
26 Correct 1200 ms 55460 KB Output is correct
27 Correct 1188 ms 57208 KB Output is correct
28 Correct 954 ms 51704 KB Output is correct
29 Correct 814 ms 56700 KB Output is correct
30 Correct 825 ms 56824 KB Output is correct
31 Correct 842 ms 55668 KB Output is correct
32 Correct 519 ms 34040 KB Output is correct
33 Correct 407 ms 29048 KB Output is correct
34 Correct 301 ms 27340 KB Output is correct
35 Correct 605 ms 55532 KB Output is correct
36 Correct 29 ms 12288 KB Output is correct
37 Correct 271 ms 30964 KB Output is correct
38 Correct 125 ms 25848 KB Output is correct
39 Correct 137 ms 30072 KB Output is correct
40 Correct 433 ms 43508 KB Output is correct
41 Correct 259 ms 30072 KB Output is correct
42 Correct 152 ms 26560 KB Output is correct
43 Correct 53 ms 14072 KB Output is correct
44 Correct 673 ms 45816 KB Output is correct
45 Correct 687 ms 45504 KB Output is correct
46 Correct 792 ms 52860 KB Output is correct
47 Correct 768 ms 51736 KB Output is correct
48 Correct 776 ms 54596 KB Output is correct
49 Correct 379 ms 36260 KB Output is correct
50 Correct 741 ms 55032 KB Output is correct
51 Correct 745 ms 55796 KB Output is correct
52 Correct 376 ms 39216 KB Output is correct
53 Correct 28 ms 13688 KB Output is correct
54 Correct 721 ms 45304 KB Output is correct
55 Correct 823 ms 51132 KB Output is correct
56 Correct 876 ms 49656 KB Output is correct
57 Correct 400 ms 37112 KB Output is correct
58 Correct 491 ms 36088 KB Output is correct
59 Correct 499 ms 36216 KB Output is correct
60 Correct 395 ms 36984 KB Output is correct
61 Correct 491 ms 36088 KB Output is correct
62 Correct 462 ms 34680 KB Output is correct
63 Correct 94 ms 15480 KB Output is correct
64 Correct 509 ms 48632 KB Output is correct
65 Correct 514 ms 49016 KB Output is correct
66 Correct 524 ms 49400 KB Output is correct
67 Correct 562 ms 49016 KB Output is correct
68 Correct 511 ms 49784 KB Output is correct
69 Correct 835 ms 50796 KB Output is correct
70 Correct 794 ms 50888 KB Output is correct
71 Correct 876 ms 52056 KB Output is correct
72 Correct 454 ms 34424 KB Output is correct
73 Correct 861 ms 53932 KB Output is correct
74 Correct 330 ms 31224 KB Output is correct
75 Correct 337 ms 33144 KB Output is correct
76 Correct 392 ms 42616 KB Output is correct
77 Correct 379 ms 34808 KB Output is correct
78 Correct 349 ms 33912 KB Output is correct
79 Correct 124 ms 25720 KB Output is correct
80 Correct 135 ms 30072 KB Output is correct
81 Correct 431 ms 43616 KB Output is correct
82 Correct 264 ms 30140 KB Output is correct
83 Correct 154 ms 26572 KB Output is correct
84 Correct 48 ms 13308 KB Output is correct
85 Correct 954 ms 48604 KB Output is correct
86 Correct 1229 ms 55948 KB Output is correct
87 Correct 71 ms 18552 KB Output is correct
88 Correct 135 ms 17656 KB Output is correct
89 Correct 71 ms 18552 KB Output is correct
90 Correct 25 ms 11648 KB Output is correct
91 Correct 8 ms 9984 KB Output is correct
92 Correct 45 ms 11904 KB Output is correct
93 Correct 444 ms 35536 KB Output is correct
94 Correct 85 ms 16888 KB Output is correct
95 Correct 927 ms 54312 KB Output is correct
96 Correct 846 ms 55028 KB Output is correct
97 Correct 875 ms 55392 KB Output is correct
98 Correct 901 ms 53908 KB Output is correct
99 Correct 1299 ms 56988 KB Output is correct
100 Correct 934 ms 57164 KB Output is correct
101 Correct 963 ms 57204 KB Output is correct
102 Correct 576 ms 37752 KB Output is correct
103 Correct 556 ms 33948 KB Output is correct
104 Correct 545 ms 35832 KB Output is correct
105 Correct 658 ms 41848 KB Output is correct
106 Correct 669 ms 41980 KB Output is correct
107 Correct 655 ms 41720 KB Output is correct
108 Correct 54 ms 13176 KB Output is correct
109 Correct 741 ms 52568 KB Output is correct
110 Correct 1201 ms 55668 KB Output is correct
111 Correct 1261 ms 55232 KB Output is correct
112 Correct 545 ms 34336 KB Output is correct
113 Correct 478 ms 34300 KB Output is correct