답안 #851867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851867 2023-09-20T17:33:23 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++14
48 / 100
4000 ms 90212 KB
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> B;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=100100;
const int M=8*N;
const int inf=(int)1e9;
int n,q,a[N];

namespace sum {
	ll c[N];
	void modify(int p,int v) {
		for (;p<N;p+=p&-p) c[p]+=v;
	}
	ll get(int p) {
		ll r=0;
		for (;p>0;p-=p&-p) r+=c[p];
		return r;
	}
	ll get(int l,int r) {
		if (l>r) {
			return 0ll;
		}
		return get(r)-get(l-1);
	}
};

namespace cnt {
	PII st[M];
	int lzy[M];
	void push(int x) {
		st[x*2].fi+=lzy[x];
		st[x*2+1].fi+=lzy[x];
		lzy[x*2]+=lzy[x];
		lzy[x*2+1]+=lzy[x];
		lzy[x]=0;
	}
	PII mrg(PII a,PII b) {
		PII r;
		r.fi=min(a.fi,b.fi);
		r.se=(a.fi==r.fi?a.se:0)+(b.fi==r.fi?b.se:0);
		return r;
	}
	void pull(int x) {
		st[x]=mrg(st[x*2],st[x*2+1]);
	}
	void build(int x,int l,int r) {
		if (l==r) {
			st[x].fi=0;
			st[x].se=1;
			return;
		}
		int mid=l+r>>1;
		build(x*2,l,mid);
		build(x*2+1,mid+1,r);
		pull(x);
	}
	void add(int x,int l,int r,int ql,int qr,int v) {
		if (l>r||l>qr||r<ql||ql>qr) {
			return;
		}
		if (ql<=l&&r<=qr) {
			st[x].fi+=v;
			lzy[x]+=v;
			push(x);
			return;
		}
		push(x);
		int mid=l+r>>1;
		add(x*2,l,mid,ql,qr,v);
		add(x*2+1,mid+1,r,ql,qr,v);
		pull(x);
	}
	PII query(int x,int l,int r,int ql,int qr) {
		if (l>r||l>qr||r<ql) {
			return mp(inf,0);
		}
		if (ql<=l&&r<=qr) {
			return st[x];
		}
		push(x);
		int mid=l+r>>1;
		auto qvl=query(x*2,l,mid,ql,qr);
		auto qvr=query(x*2+1,mid+1,r,ql,qr);
		pull(x);
		return mrg(qvl,qvr);
	}
	int sol(int l,int r) {
		auto p=query(1,1,n,l,r);
		return p.se;
	}
};

vector<PII> my;
namespace segs {
	multiset<PII> st[M];
	void add(int x,int l,int r,int ql,int qr,PII p) {
		if (l>r||l>qr||r<ql) {
			return;
		}
		if (ql<=l&&r<=qr) {
			st[x].insert(p);
			return;
		}
		int mid=l+r>>1;
		add(x*2,l,mid,ql,qr,p);
		add(x*2+1,mid+1,r,ql,qr,p);
	}
	void rem(int x,int l,int r,PII p) {
		if (l>r||l>p.se||r<p.fi) {
			return;
		}
		if (p.fi<=l&&r<=p.se) {
			st[x].erase(st[x].find(p));
			return;
		}
		int mid=l+r>>1;
		rem(x*2,l,mid,p);
		rem(x*2+1,mid+1,r,p);
	}
	void dfs(int x,int l,int r,int p) {
		while (SZ(st[x])) {
			auto p=*st[x].begin();
			cnt::add(1,1,n,p.fi+1,p.se-1,-1);
			rem(1,1,n,p);
		}
		st[x].clear();
		if (l==r) {
			return;
		}
		int mid=l+r>>1;
		if (p<=mid) {
			dfs(x*2,l,mid,p);
		} else {
			dfs(x*2+1,mid+1,r,p);
		}
	}
};

namespace pref {
	struct node {
		ll vl,vr,lzyl,lzyr;
		node(ll _vl=0,ll _vr=0,ll tg1=0,ll tg2=0) : vl(_vl),vr(_vr),lzyl(tg1),lzyr(tg2) {}
	};
	node st[M];
	node mrg(node a,node b) {
		node r;
		r.vl=max(a.vl,b.vl);
		r.vr=max(a.vr,b.vr);
		return r;
	}
	void pull(int x) {
		st[x]=mrg(st[x*2],st[x*2+1]);
	}
	void push(int x) {
		st[x*2].vl+=st[x].lzyl;
		st[x*2+1].vl+=st[x].lzyl;
		st[x*2].lzyl+=st[x].lzyl;
		st[x*2+1].lzyl+=st[x].lzyl;
		st[x].lzyl=0;
		st[x*2].vr+=st[x].lzyr;
		st[x*2+1].vr+=st[x].lzyr;
		st[x*2].lzyr+=st[x].lzyr;
		st[x*2+1].lzyr+=st[x].lzyr;
		st[x].lzyr=0;
	}
	void build(int x,int l,int r) {
		if (l==r) {
			st[x].vl=a[l]-sum::get(1,l-1);
			st[x].vr=a[l]-sum::get(l+1,N-1);
			st[x].lzyl=0;
			st[x].lzyr=0;
			return;
		}
		int mid=l+r>>1;
		build(x*2,l,mid);
		build(x*2+1,mid+1,r);
		pull(x);
	}
	void modifyL(int x,int l,int r,int ql,int qr,ll v) {
		if (l>r||l>qr||r<ql||ql>qr) {
			return;
		}
		if (ql<=l&&r<=qr) {
			st[x].lzyl+=v;
			st[x].vl+=v;
			push(x);
			return;
		}
		push(x);
		int mid=l+r>>1;
		modifyL(x*2,l,mid,ql,qr,v);
		modifyL(x*2+1,mid+1,r,ql,qr,v);
		pull(x);
	}
	void modifyR(int x,int l,int r,int ql,int qr,ll v) {
		if (l>r||l>qr||r<ql||ql>qr) {
			return;
		}
		if (ql<=l&&r<=qr) {
			st[x].lzyr+=v;
			st[x].vr+=v;
			push(x);
			return;
		}
		push(x);
		int mid=l+r>>1;
		modifyR(x*2,l,mid,ql,qr,v);
		modifyR(x*2+1,mid+1,r,ql,qr,v);
		pull(x);
	}
	node query(int x,int l,int r,int ql,int qr) {
		if (l>r||l>qr||r<ql||ql>qr) {
			return node(-inf*1ll*inf,-inf*1ll*inf,0ll,0ll);
		}
		if (ql<=l&&r<=qr) {
			return st[x];
		}
		push(x);
		int mid=l+r>>1;
		node qvl=query(x*2,l,mid,ql,qr);
		node qvr=query(x*2+1,mid+1,r,ql,qr);
		pull(x);
		return mrg(qvl,qvr);
	}
};

void build() {
	cnt::build(1,1,n);
	rep(i,1,n+1) {
		sum::modify(i,a[i]);
	}
	pref::build(1,1,n);
	stack<int> stk;
	rep(i,1,n+1) {
		while (SZ(stk)>0&&a[i]>a[stk.top()]) {
			int L=stk.top();
			int R=i;
			if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
				segs::add(1,1,n,L,R,mp(L,R));
				cnt::add(1,1,n,L+1,R-1,1);
			}
			stk.pop();
		}
		stk.push(i);
	}
	while (SZ(stk)) stk.pop();
	per(i,1,n+1) {
		while (SZ(stk)>0&&a[i]>=a[stk.top()]) {
			int L=i;
			int R=stk.top();
			if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
				segs::add(1,1,n,L,R,mp(L,R));
				cnt::add(1,1,n,L+1,R-1,1);
			}
			stk.pop();
		}
		stk.push(i);
	}
}

int main() {
	scanf("%d",&n);
	rep(i,1,n+1) {
		scanf("%d",&a[i]);
	}
	build();
	scanf("%d",&q);
	while (q--) {
		int op;
		scanf("%d",&op);
		if (op==1) {
			int i,x;
			scanf("%d%d",&i,&x);
			sum::modify(i,-a[i]);
			sum::modify(i,x);
			pref::modifyL(1,1,n,i,i,-a[i]+x);
			pref::modifyR(1,1,n,i,i,-a[i]+x);
			if (i!=n) pref::modifyL(1,1,n,i+1,n,a[i]-x);
			if (i!=1) pref::modifyR(1,1,n,1,i-1,a[i]-x);
			a[i]=x;
			my.clear();
			segs::dfs(1,1,n,i);
			for (auto& p:my) {
				if (min(a[p.fi],a[p.se])>sum::get(p.fi+1,p.se-1)) {
					segs::add(1,1,n,p.fi,p.se,p);
					cnt::add(1,1,n,p.fi+1,p.se-1,1);
				}
			}
			VI L(1,i),R(1,i);
			{
				ll ft=sum::get(i,n);
				int cur=i-1;
				while (cur>0&&pref::query(1,1,n,1,cur).vr+ft>0) {
					int low=1,high=cur,pos=cur;
					while (low<=high) {
						int mid=low+high>>1;
						if (pref::query(1,1,n,mid,cur).vr+ft>0) {
							pos=mid;
							low=mid+1;
						} else {
							high=mid-1;
						}
					}
					L.pb(pos);
					cur=pos-1;
				}
			}
			{
				ll ft=sum::get(1,i);
				int cur=i+1;
				while (cur<=n&&pref::query(1,1,n,cur,n).vl+ft>0) {
					int low=cur,high=n,pos=cur;
					while (low<=high) {
						int mid=low+high>>1;
						if (pref::query(1,1,n,cur,mid).vl+ft>0) {
							pos=mid;
							high=mid-1;
						} else {
							low=mid+1;
						}
					}
					R.pb(pos);
					cur=pos+1;
				}
			}
			//rep(j,1,i) if (a[j]>sum::get(j+1,i-1)) L.pb(j);
			//rep(j,i+1,n+1) if (a[j]>sum::get(i+1,j-1)) R.pb(j);
			for (int x:L) {
				for (int y:R) {
					if (x+1<y&&min(a[x],a[y])>sum::get(x+1,y-1)) {
						segs::add(1,1,n,x,y,mp(x,y));
						cnt::add(1,1,n,x+1,y-1,1);
					}
				}
			}
		} else {
			int l,r;
			scanf("%d%d",&l,&r);
			{
				int low=l,high=r,pos=l;
				while (low<=high) {
					int mid=low+high>>1;
					if (pref::query(1,1,n,mid,r).vl+sum::get(1,l-1)>0) {
						pos=mid;
						low=mid+1;
					} else {
						high=mid-1;
					}
				}
				l=pos;
			}
			{
				int low=l,high=r,pos=r;
				while (low<=high) {
					int mid=low+high>>1;
					if (pref::query(1,1,n,l,mid).vr+sum::get(r+1,n)>0) {
						pos=mid;
						high=mid-1;
					} else {
						low=mid+1;
					}
				}
				r=pos;
			}
			//printf("-- %d %d --\n",l,r);
			printf("%d\n",cnt::sol(l,r));
		}
	}
}

Compilation message

fish2.cpp: In function 'void cnt::build(int, int, int)':
fish2.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void cnt::add(int, int, int, int, int, int)':
fish2.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'PII cnt::query(int, int, int, int, int)':
fish2.cpp:101:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void segs::add(int, int, int, int, int, PII)':
fish2.cpp:124:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void segs::rem(int, int, int, PII)':
fish2.cpp:136:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void segs::dfs(int, int, int, int)':
fish2.cpp:150:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void pref::build(int, int, int)':
fish2.cpp:194:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  194 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void pref::modifyL(int, int, int, int, int, ll)':
fish2.cpp:210:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  210 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void pref::modifyR(int, int, int, int, int, ll)':
fish2.cpp:226:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  226 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'pref::node pref::query(int, int, int, int, int)':
fish2.cpp:239:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  239 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'int main()':
fish2.cpp:316:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  316 |       int mid=low+high>>1;
      |               ~~~^~~~~
fish2.cpp:334:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  334 |       int mid=low+high>>1;
      |               ~~~^~~~~
fish2.cpp:362:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  362 |      int mid=low+high>>1;
      |              ~~~^~~~~
fish2.cpp:375:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  375 |      int mid=low+high>>1;
      |              ~~~^~~~~
fish2.cpp:282:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  282 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:284:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  284 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
fish2.cpp:287:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:290:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  290 |   scanf("%d",&op);
      |   ~~~~~^~~~~~~~~~
fish2.cpp:293:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  293 |    scanf("%d%d",&i,&x);
      |    ~~~~~^~~~~~~~~~~~~~
fish2.cpp:358:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  358 |    scanf("%d%d",&l,&r);
      |    ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 66140 KB Output is correct
2 Correct 11 ms 66136 KB Output is correct
3 Correct 11 ms 66136 KB Output is correct
4 Correct 11 ms 66136 KB Output is correct
5 Correct 24 ms 68440 KB Output is correct
6 Correct 16 ms 68384 KB Output is correct
7 Correct 24 ms 68184 KB Output is correct
8 Correct 18 ms 68184 KB Output is correct
9 Correct 16 ms 68184 KB Output is correct
10 Correct 15 ms 68184 KB Output is correct
11 Correct 13 ms 68184 KB Output is correct
12 Correct 17 ms 68184 KB Output is correct
13 Correct 15 ms 68184 KB Output is correct
14 Correct 15 ms 68412 KB Output is correct
15 Correct 17 ms 68440 KB Output is correct
16 Correct 14 ms 68184 KB Output is correct
17 Correct 16 ms 68184 KB Output is correct
18 Correct 14 ms 68184 KB Output is correct
19 Correct 15 ms 68184 KB Output is correct
20 Correct 15 ms 68184 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 66136 KB Output is correct
2 Correct 92 ms 87532 KB Output is correct
3 Correct 85 ms 84048 KB Output is correct
4 Correct 104 ms 87376 KB Output is correct
5 Correct 92 ms 84816 KB Output is correct
6 Correct 51 ms 75600 KB Output is correct
7 Correct 45 ms 74488 KB Output is correct
8 Correct 49 ms 75604 KB Output is correct
9 Correct 40 ms 74320 KB Output is correct
10 Correct 59 ms 79176 KB Output is correct
11 Correct 53 ms 78372 KB Output is correct
12 Correct 47 ms 75224 KB Output is correct
13 Correct 45 ms 75344 KB Output is correct
14 Correct 60 ms 78484 KB Output is correct
15 Correct 63 ms 78416 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 66140 KB Output is correct
2 Correct 11 ms 66136 KB Output is correct
3 Correct 11 ms 66136 KB Output is correct
4 Correct 11 ms 66136 KB Output is correct
5 Correct 24 ms 68440 KB Output is correct
6 Correct 16 ms 68384 KB Output is correct
7 Correct 24 ms 68184 KB Output is correct
8 Correct 18 ms 68184 KB Output is correct
9 Correct 16 ms 68184 KB Output is correct
10 Correct 15 ms 68184 KB Output is correct
11 Correct 13 ms 68184 KB Output is correct
12 Correct 17 ms 68184 KB Output is correct
13 Correct 15 ms 68184 KB Output is correct
14 Correct 15 ms 68412 KB Output is correct
15 Correct 17 ms 68440 KB Output is correct
16 Correct 14 ms 68184 KB Output is correct
17 Correct 16 ms 68184 KB Output is correct
18 Correct 14 ms 68184 KB Output is correct
19 Correct 15 ms 68184 KB Output is correct
20 Correct 15 ms 68184 KB Output is correct
21 Correct 11 ms 66136 KB Output is correct
22 Correct 92 ms 87532 KB Output is correct
23 Correct 85 ms 84048 KB Output is correct
24 Correct 104 ms 87376 KB Output is correct
25 Correct 92 ms 84816 KB Output is correct
26 Correct 51 ms 75600 KB Output is correct
27 Correct 45 ms 74488 KB Output is correct
28 Correct 49 ms 75604 KB Output is correct
29 Correct 40 ms 74320 KB Output is correct
30 Correct 59 ms 79176 KB Output is correct
31 Correct 53 ms 78372 KB Output is correct
32 Correct 47 ms 75224 KB Output is correct
33 Correct 45 ms 75344 KB Output is correct
34 Correct 60 ms 78484 KB Output is correct
35 Correct 63 ms 78416 KB Output is correct
36 Correct 185 ms 89684 KB Output is correct
37 Correct 125 ms 84684 KB Output is correct
38 Correct 94 ms 83024 KB Output is correct
39 Correct 190 ms 89520 KB Output is correct
40 Correct 106 ms 82848 KB Output is correct
41 Correct 69 ms 75600 KB Output is correct
42 Correct 81 ms 75656 KB Output is correct
43 Correct 73 ms 74608 KB Output is correct
44 Correct 61 ms 74320 KB Output is correct
45 Correct 138 ms 81212 KB Output is correct
46 Correct 79 ms 79744 KB Output is correct
47 Correct 59 ms 75088 KB Output is correct
48 Correct 95 ms 75432 KB Output is correct
49 Correct 63 ms 75344 KB Output is correct
50 Correct 87 ms 78576 KB Output is correct
51 Correct 84 ms 78600 KB Output is correct
52 Correct 77 ms 78416 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 66136 KB Output is correct
2 Correct 92 ms 87532 KB Output is correct
3 Correct 85 ms 84048 KB Output is correct
4 Correct 104 ms 87376 KB Output is correct
5 Correct 92 ms 84816 KB Output is correct
6 Correct 51 ms 75600 KB Output is correct
7 Correct 45 ms 74488 KB Output is correct
8 Correct 49 ms 75604 KB Output is correct
9 Correct 40 ms 74320 KB Output is correct
10 Correct 59 ms 79176 KB Output is correct
11 Correct 53 ms 78372 KB Output is correct
12 Correct 47 ms 75224 KB Output is correct
13 Correct 45 ms 75344 KB Output is correct
14 Correct 60 ms 78484 KB Output is correct
15 Correct 63 ms 78416 KB Output is correct
16 Correct 11 ms 66140 KB Output is correct
17 Correct 1543 ms 84500 KB Output is correct
18 Correct 1585 ms 89940 KB Output is correct
19 Correct 1552 ms 85528 KB Output is correct
20 Correct 1562 ms 85552 KB Output is correct
21 Correct 1575 ms 84836 KB Output is correct
22 Correct 1601 ms 90212 KB Output is correct
23 Correct 1585 ms 84988 KB Output is correct
24 Correct 1553 ms 86172 KB Output is correct
25 Correct 1617 ms 85828 KB Output is correct
26 Correct 1553 ms 86132 KB Output is correct
27 Correct 1560 ms 76192 KB Output is correct
28 Correct 1594 ms 76772 KB Output is correct
29 Correct 1579 ms 76752 KB Output is correct
30 Correct 1259 ms 74744 KB Output is correct
31 Correct 1190 ms 74592 KB Output is correct
32 Correct 1561 ms 79004 KB Output is correct
33 Correct 1600 ms 79900 KB Output is correct
34 Correct 1504 ms 78068 KB Output is correct
35 Correct 1543 ms 76556 KB Output is correct
36 Correct 1631 ms 81236 KB Output is correct
37 Correct 1420 ms 75752 KB Output is correct
38 Correct 1355 ms 75696 KB Output is correct
39 Correct 1561 ms 78992 KB Output is correct
40 Correct 1818 ms 79696 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 66136 KB Output is correct
2 Correct 92 ms 87532 KB Output is correct
3 Correct 85 ms 84048 KB Output is correct
4 Correct 104 ms 87376 KB Output is correct
5 Correct 92 ms 84816 KB Output is correct
6 Correct 51 ms 75600 KB Output is correct
7 Correct 45 ms 74488 KB Output is correct
8 Correct 49 ms 75604 KB Output is correct
9 Correct 40 ms 74320 KB Output is correct
10 Correct 59 ms 79176 KB Output is correct
11 Correct 53 ms 78372 KB Output is correct
12 Correct 47 ms 75224 KB Output is correct
13 Correct 45 ms 75344 KB Output is correct
14 Correct 60 ms 78484 KB Output is correct
15 Correct 63 ms 78416 KB Output is correct
16 Correct 12 ms 66136 KB Output is correct
17 Execution timed out 4008 ms 87684 KB Time limit exceeded
18 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 66140 KB Output is correct
2 Correct 11 ms 66136 KB Output is correct
3 Correct 11 ms 66136 KB Output is correct
4 Correct 11 ms 66136 KB Output is correct
5 Correct 24 ms 68440 KB Output is correct
6 Correct 16 ms 68384 KB Output is correct
7 Correct 24 ms 68184 KB Output is correct
8 Correct 18 ms 68184 KB Output is correct
9 Correct 16 ms 68184 KB Output is correct
10 Correct 15 ms 68184 KB Output is correct
11 Correct 13 ms 68184 KB Output is correct
12 Correct 17 ms 68184 KB Output is correct
13 Correct 15 ms 68184 KB Output is correct
14 Correct 15 ms 68412 KB Output is correct
15 Correct 17 ms 68440 KB Output is correct
16 Correct 14 ms 68184 KB Output is correct
17 Correct 16 ms 68184 KB Output is correct
18 Correct 14 ms 68184 KB Output is correct
19 Correct 15 ms 68184 KB Output is correct
20 Correct 15 ms 68184 KB Output is correct
21 Correct 11 ms 66136 KB Output is correct
22 Correct 92 ms 87532 KB Output is correct
23 Correct 85 ms 84048 KB Output is correct
24 Correct 104 ms 87376 KB Output is correct
25 Correct 92 ms 84816 KB Output is correct
26 Correct 51 ms 75600 KB Output is correct
27 Correct 45 ms 74488 KB Output is correct
28 Correct 49 ms 75604 KB Output is correct
29 Correct 40 ms 74320 KB Output is correct
30 Correct 59 ms 79176 KB Output is correct
31 Correct 53 ms 78372 KB Output is correct
32 Correct 47 ms 75224 KB Output is correct
33 Correct 45 ms 75344 KB Output is correct
34 Correct 60 ms 78484 KB Output is correct
35 Correct 63 ms 78416 KB Output is correct
36 Correct 185 ms 89684 KB Output is correct
37 Correct 125 ms 84684 KB Output is correct
38 Correct 94 ms 83024 KB Output is correct
39 Correct 190 ms 89520 KB Output is correct
40 Correct 106 ms 82848 KB Output is correct
41 Correct 69 ms 75600 KB Output is correct
42 Correct 81 ms 75656 KB Output is correct
43 Correct 73 ms 74608 KB Output is correct
44 Correct 61 ms 74320 KB Output is correct
45 Correct 138 ms 81212 KB Output is correct
46 Correct 79 ms 79744 KB Output is correct
47 Correct 59 ms 75088 KB Output is correct
48 Correct 95 ms 75432 KB Output is correct
49 Correct 63 ms 75344 KB Output is correct
50 Correct 87 ms 78576 KB Output is correct
51 Correct 84 ms 78600 KB Output is correct
52 Correct 77 ms 78416 KB Output is correct
53 Correct 11 ms 66140 KB Output is correct
54 Correct 1543 ms 84500 KB Output is correct
55 Correct 1585 ms 89940 KB Output is correct
56 Correct 1552 ms 85528 KB Output is correct
57 Correct 1562 ms 85552 KB Output is correct
58 Correct 1575 ms 84836 KB Output is correct
59 Correct 1601 ms 90212 KB Output is correct
60 Correct 1585 ms 84988 KB Output is correct
61 Correct 1553 ms 86172 KB Output is correct
62 Correct 1617 ms 85828 KB Output is correct
63 Correct 1553 ms 86132 KB Output is correct
64 Correct 1560 ms 76192 KB Output is correct
65 Correct 1594 ms 76772 KB Output is correct
66 Correct 1579 ms 76752 KB Output is correct
67 Correct 1259 ms 74744 KB Output is correct
68 Correct 1190 ms 74592 KB Output is correct
69 Correct 1561 ms 79004 KB Output is correct
70 Correct 1600 ms 79900 KB Output is correct
71 Correct 1504 ms 78068 KB Output is correct
72 Correct 1543 ms 76556 KB Output is correct
73 Correct 1631 ms 81236 KB Output is correct
74 Correct 1420 ms 75752 KB Output is correct
75 Correct 1355 ms 75696 KB Output is correct
76 Correct 1561 ms 78992 KB Output is correct
77 Correct 1818 ms 79696 KB Output is correct
78 Correct 12 ms 66136 KB Output is correct
79 Execution timed out 4008 ms 87684 KB Time limit exceeded
80 Halted 0 ms 0 KB -