oj.uz

Submission #851876

# Submission time Handle Problem Language Result Execution time Memory
851876 2023-09-20T17:55:48 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++14
48 / 100
 4000 ms 66396 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 {
	vector<PII> st[M];
	multiset<PII> all;
	void add(int x,int l,int r,int ql,int qr,PII p) {
		if (x==1) all.insert(p);
		if (l>r||l>qr||r<ql) {
			return;
		}
		if (ql<=l&&r<=qr) {
			st[x].pb(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) {
		for (auto& p:st[x]) {
			if (all.find(p)!=all.end()) {
				all.erase(all.find(p));
				cnt::add(1,1,n,p.fi+1,p.se-1,-1);
			}
		}
		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);
	}
	int walkL(int x,int l,int r,int ql,int qr,ll ft) {
		if (l>qr||st[x].vr+ft<=0) return -1;
		if (l==r) {
			return l;
		}
		push(x);
		int res=-1;
		int mid=l+r>>1;
		if (r<=qr) {
			if (st[x*2+1].vr+ft>0) res=walkL(x*2+1,mid+1,r,ql,qr,ft);
			else res=walkL(x*2,l,mid,ql,qr,ft);
		} else {
			res=walkL(x*2+1,mid+1,r,ql,qr,ft);
			if (res==-1) {
				res=walkL(x*2,l,mid,ql,qr,ft);
			}
		}
		pull(x);
		return res;
	}
};

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 pos=pref::walkL(1,1,n,1,cur,ft);
					/* 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 pos=pref::walkR(1,1,n,cur,n,ft);
					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:126:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void segs::dfs(int, int, int, int)':
fish2.cpp:153:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void pref::build(int, int, int)':
fish2.cpp:197:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  197 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void pref::modifyL(int, int, int, int, int, ll)':
fish2.cpp:213:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  213 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void pref::modifyR(int, int, int, int, int, ll)':
fish2.cpp:229:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  229 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'pref::node pref::query(int, int, int, int, int)':
fish2.cpp:242:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  242 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'int pref::walkL(int, int, int, int, int, ll)':
fish2.cpp:255:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  255 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'int main()':
fish2.cpp:359:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  359 |       int mid=low+high>>1;
      |               ~~~^~~~~
fish2.cpp:387:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  387 |      int mid=low+high>>1;
      |              ~~~^~~~~
fish2.cpp:400:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  400 |      int mid=low+high>>1;
      |              ~~~^~~~~
fish2.cpp:305:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  305 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:307:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  307 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
fish2.cpp:310:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  310 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:313:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  313 |   scanf("%d",&op);
      |   ~~~~~^~~~~~~~~~
fish2.cpp:316:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  316 |    scanf("%d%d",&i,&x);
      |    ~~~~~^~~~~~~~~~~~~~
fish2.cpp:383:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  383 |    scanf("%d%d",&l,&r);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 49956 KB Output is correct
2 Correct 10 ms 49752 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Correct 9 ms 49756 KB Output is correct
5 Correct 21 ms 49752 KB Output is correct
6 Correct 13 ms 49756 KB Output is correct
7 Correct 20 ms 49924 KB Output is correct
8 Correct 15 ms 49752 KB Output is correct
9 Correct 12 ms 49752 KB Output is correct
10 Correct 11 ms 49752 KB Output is correct
11 Correct 10 ms 49752 KB Output is correct
12 Correct 13 ms 49752 KB Output is correct
13 Correct 12 ms 49916 KB Output is correct
14 Correct 15 ms 49756 KB Output is correct
15 Correct 12 ms 49752 KB Output is correct
16 Correct 12 ms 49888 KB Output is correct
17 Correct 12 ms 49752 KB Output is correct
18 Correct 10 ms 50008 KB Output is correct
19 Correct 11 ms 49752 KB Output is correct
20 Correct 11 ms 49752 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 50008 KB Output is correct
2 Correct 80 ms 64080 KB Output is correct
3 Correct 82 ms 63056 KB Output is correct
4 Correct 99 ms 64084 KB Output is correct
5 Correct 84 ms 63064 KB Output is correct
6 Correct 52 ms 59216 KB Output is correct
7 Correct 40 ms 57684 KB Output is correct
8 Correct 58 ms 59132 KB Output is correct
9 Correct 42 ms 57680 KB Output is correct
10 Correct 57 ms 59984 KB Output is correct
11 Correct 51 ms 59544 KB Output is correct
12 Correct 47 ms 58704 KB Output is correct
13 Correct 58 ms 58704 KB Output is correct
14 Correct 69 ms 61484 KB Output is correct
15 Correct 65 ms 61012 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 49956 KB Output is correct
2 Correct 10 ms 49752 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Correct 9 ms 49756 KB Output is correct
5 Correct 21 ms 49752 KB Output is correct
6 Correct 13 ms 49756 KB Output is correct
7 Correct 20 ms 49924 KB Output is correct
8 Correct 15 ms 49752 KB Output is correct
9 Correct 12 ms 49752 KB Output is correct
10 Correct 11 ms 49752 KB Output is correct
11 Correct 10 ms 49752 KB Output is correct
12 Correct 13 ms 49752 KB Output is correct
13 Correct 12 ms 49916 KB Output is correct
14 Correct 15 ms 49756 KB Output is correct
15 Correct 12 ms 49752 KB Output is correct
16 Correct 12 ms 49888 KB Output is correct
17 Correct 12 ms 49752 KB Output is correct
18 Correct 10 ms 50008 KB Output is correct
19 Correct 11 ms 49752 KB Output is correct
20 Correct 11 ms 49752 KB Output is correct
21 Correct 8 ms 50008 KB Output is correct
22 Correct 80 ms 64080 KB Output is correct
23 Correct 82 ms 63056 KB Output is correct
24 Correct 99 ms 64084 KB Output is correct
25 Correct 84 ms 63064 KB Output is correct
26 Correct 52 ms 59216 KB Output is correct
27 Correct 40 ms 57684 KB Output is correct
28 Correct 58 ms 59132 KB Output is correct
29 Correct 42 ms 57680 KB Output is correct
30 Correct 57 ms 59984 KB Output is correct
31 Correct 51 ms 59544 KB Output is correct
32 Correct 47 ms 58704 KB Output is correct
33 Correct 58 ms 58704 KB Output is correct
34 Correct 69 ms 61484 KB Output is correct
35 Correct 65 ms 61012 KB Output is correct
36 Correct 146 ms 65360 KB Output is correct
37 Correct 118 ms 63568 KB Output is correct
38 Correct 104 ms 62752 KB Output is correct
39 Correct 223 ms 65872 KB Output is correct
40 Correct 96 ms 62516 KB Output is correct
41 Correct 71 ms 60004 KB Output is correct
42 Correct 72 ms 59984 KB Output is correct
43 Correct 70 ms 57948 KB Output is correct
44 Correct 72 ms 57992 KB Output is correct
45 Correct 115 ms 61624 KB Output is correct
46 Correct 75 ms 60496 KB Output is correct
47 Correct 65 ms 58192 KB Output is correct
48 Correct 85 ms 59572 KB Output is correct
49 Correct 64 ms 59216 KB Output is correct
50 Correct 83 ms 61776 KB Output is correct
51 Correct 85 ms 61520 KB Output is correct
52 Correct 95 ms 61964 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 50008 KB Output is correct
2 Correct 80 ms 64080 KB Output is correct
3 Correct 82 ms 63056 KB Output is correct
4 Correct 99 ms 64084 KB Output is correct
5 Correct 84 ms 63064 KB Output is correct
6 Correct 52 ms 59216 KB Output is correct
7 Correct 40 ms 57684 KB Output is correct
8 Correct 58 ms 59132 KB Output is correct
9 Correct 42 ms 57680 KB Output is correct
10 Correct 57 ms 59984 KB Output is correct
11 Correct 51 ms 59544 KB Output is correct
12 Correct 47 ms 58704 KB Output is correct
13 Correct 58 ms 58704 KB Output is correct
14 Correct 69 ms 61484 KB Output is correct
15 Correct 65 ms 61012 KB Output is correct
16 Correct 8 ms 49752 KB Output is correct
17 Correct 1578 ms 63516 KB Output is correct
18 Correct 1643 ms 65948 KB Output is correct
19 Correct 1601 ms 64080 KB Output is correct
20 Correct 1624 ms 64104 KB Output is correct
21 Correct 1570 ms 63632 KB Output is correct
22 Correct 1627 ms 65688 KB Output is correct
23 Correct 1612 ms 63824 KB Output is correct
24 Correct 1621 ms 64088 KB Output is correct
25 Correct 1679 ms 64036 KB Output is correct
26 Correct 1602 ms 64336 KB Output is correct
27 Correct 1713 ms 60080 KB Output is correct
28 Correct 1564 ms 60280 KB Output is correct
29 Correct 1611 ms 60016 KB Output is correct
30 Correct 1281 ms 57988 KB Output is correct
31 Correct 1166 ms 58168 KB Output is correct
32 Correct 1536 ms 60556 KB Output is correct
33 Correct 1586 ms 60468 KB Output is correct
34 Correct 1507 ms 59204 KB Output is correct
35 Correct 1487 ms 58464 KB Output is correct
36 Correct 1597 ms 60880 KB Output is correct
37 Correct 1399 ms 59372 KB Output is correct
38 Correct 1432 ms 59440 KB Output is correct
39 Correct 1594 ms 62392 KB Output is correct
40 Correct 1832 ms 61828 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 50008 KB Output is correct
2 Correct 80 ms 64080 KB Output is correct
3 Correct 82 ms 63056 KB Output is correct
4 Correct 99 ms 64084 KB Output is correct
5 Correct 84 ms 63064 KB Output is correct
6 Correct 52 ms 59216 KB Output is correct
7 Correct 40 ms 57684 KB Output is correct
8 Correct 58 ms 59132 KB Output is correct
9 Correct 42 ms 57680 KB Output is correct
10 Correct 57 ms 59984 KB Output is correct
11 Correct 51 ms 59544 KB Output is correct
12 Correct 47 ms 58704 KB Output is correct
13 Correct 58 ms 58704 KB Output is correct
14 Correct 69 ms 61484 KB Output is correct
15 Correct 65 ms 61012 KB Output is correct
16 Correct 9 ms 49912 KB Output is correct
17 Execution timed out 4099 ms 66396 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 49956 KB Output is correct
2 Correct 10 ms 49752 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Correct 9 ms 49756 KB Output is correct
5 Correct 21 ms 49752 KB Output is correct
6 Correct 13 ms 49756 KB Output is correct
7 Correct 20 ms 49924 KB Output is correct
8 Correct 15 ms 49752 KB Output is correct
9 Correct 12 ms 49752 KB Output is correct
10 Correct 11 ms 49752 KB Output is correct
11 Correct 10 ms 49752 KB Output is correct
12 Correct 13 ms 49752 KB Output is correct
13 Correct 12 ms 49916 KB Output is correct
14 Correct 15 ms 49756 KB Output is correct
15 Correct 12 ms 49752 KB Output is correct
16 Correct 12 ms 49888 KB Output is correct
17 Correct 12 ms 49752 KB Output is correct
18 Correct 10 ms 50008 KB Output is correct
19 Correct 11 ms 49752 KB Output is correct
20 Correct 11 ms 49752 KB Output is correct
21 Correct 8 ms 50008 KB Output is correct
22 Correct 80 ms 64080 KB Output is correct
23 Correct 82 ms 63056 KB Output is correct
24 Correct 99 ms 64084 KB Output is correct
25 Correct 84 ms 63064 KB Output is correct
26 Correct 52 ms 59216 KB Output is correct
27 Correct 40 ms 57684 KB Output is correct
28 Correct 58 ms 59132 KB Output is correct
29 Correct 42 ms 57680 KB Output is correct
30 Correct 57 ms 59984 KB Output is correct
31 Correct 51 ms 59544 KB Output is correct
32 Correct 47 ms 58704 KB Output is correct
33 Correct 58 ms 58704 KB Output is correct
34 Correct 69 ms 61484 KB Output is correct
35 Correct 65 ms 61012 KB Output is correct
36 Correct 146 ms 65360 KB Output is correct
37 Correct 118 ms 63568 KB Output is correct
38 Correct 104 ms 62752 KB Output is correct
39 Correct 223 ms 65872 KB Output is correct
40 Correct 96 ms 62516 KB Output is correct
41 Correct 71 ms 60004 KB Output is correct
42 Correct 72 ms 59984 KB Output is correct
43 Correct 70 ms 57948 KB Output is correct
44 Correct 72 ms 57992 KB Output is correct
45 Correct 115 ms 61624 KB Output is correct
46 Correct 75 ms 60496 KB Output is correct
47 Correct 65 ms 58192 KB Output is correct
48 Correct 85 ms 59572 KB Output is correct
49 Correct 64 ms 59216 KB Output is correct
50 Correct 83 ms 61776 KB Output is correct
51 Correct 85 ms 61520 KB Output is correct
52 Correct 95 ms 61964 KB Output is correct
53 Correct 8 ms 49752 KB Output is correct
54 Correct 1578 ms 63516 KB Output is correct
55 Correct 1643 ms 65948 KB Output is correct
56 Correct 1601 ms 64080 KB Output is correct
57 Correct 1624 ms 64104 KB Output is correct
58 Correct 1570 ms 63632 KB Output is correct
59 Correct 1627 ms 65688 KB Output is correct
60 Correct 1612 ms 63824 KB Output is correct
61 Correct 1621 ms 64088 KB Output is correct
62 Correct 1679 ms 64036 KB Output is correct
63 Correct 1602 ms 64336 KB Output is correct
64 Correct 1713 ms 60080 KB Output is correct
65 Correct 1564 ms 60280 KB Output is correct
66 Correct 1611 ms 60016 KB Output is correct
67 Correct 1281 ms 57988 KB Output is correct
68 Correct 1166 ms 58168 KB Output is correct
69 Correct 1536 ms 60556 KB Output is correct
70 Correct 1586 ms 60468 KB Output is correct
71 Correct 1507 ms 59204 KB Output is correct
72 Correct 1487 ms 58464 KB Output is correct
73 Correct 1597 ms 60880 KB Output is correct
74 Correct 1399 ms 59372 KB Output is correct
75 Correct 1432 ms 59440 KB Output is correct
76 Correct 1594 ms 62392 KB Output is correct
77 Correct 1832 ms 61828 KB Output is correct
78 Correct 9 ms 49912 KB Output is correct
79 Execution timed out 4099 ms 66396 KB Time limit exceeded
80 Halted 0 ms 0 KB -