oj.uz

Submission #589745

# Submission time Handle Problem Language Result Execution time Memory
589745 2022-07-05T08:28:41 Z 8e7 Fish 2 (JOI22_fish2) C++17
100 / 100
 1903 ms 291412 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;

struct segtree_interval{
	stack<pii> stk[4*maxn];	
	bool in (pii &p, int x) {
		return p.ff <= x && x <= p.ss;
	}
	void remove(int cur, int l, int r, int ind, vector<pii> &v) {
		if (r <= l) return;
		while (stk[cur].size() && in(stk[cur].top(), ind)) {
			v.push_back(stk[cur].top());
			stk[cur].pop();
		}
		int m = (l + r) / 2;
		if (ind < m) remove(cur*2, l, m, ind, v);
		else if (ind > m) remove(cur*2+1, m+1, r, ind, v);
	}
	void ins(int cur, int l, int r, pii p) {
		if (r <= l) return;
		int m = (l + r) / 2;
		if (in(p, m)) {
			stk[cur].push(p);
			return;
		}
		if (m > p.ss) ins(cur*2, l, m, p);
		else if (m < p.ff) ins(cur*2+1, m+1, r, p);
	}
} inter;
struct segtree_mincnt{
	pii seg[4*maxn];
	int tag[4*maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		seg[cur].ss = (r - l);
		if (r - l == 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
	}
	void push(int cur, int l, int r) {
		seg[cur].ff += tag[cur];
		if (r - l > 1) {
			tag[cur*2] += tag[cur];
			tag[cur*2+1] += tag[cur];
		}
		tag[cur] = 0;
	}
	void merge(pii &a, pii &b, pii &c) {
		a.ff = min(b.ff, c.ff);
		a.ss = (b.ff == a.ff ? b.ss : 0) + (c.ff == a.ff ? c.ss : 0);
	}
	void pull(int cur, int l, int r) {
		int m = (l + r) / 2;
		push(cur*2, l, m), push(cur*2+1, m, r);
		merge(seg[cur], seg[cur*2], seg[cur*2+1]);
	}
	void modify(int cur, int l, int r, int ql, int qr, int v) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += v;
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v); 
		modify(cur*2+1, m, r, ql, qr, v); 
		pull(cur, l, r);
	}
	pii query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return {inf, 0};
		push(cur, l, r);
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		pii ret, vl = query(cur*2, l, m, ql, qr), vr = query(cur*2+1, m, r, ql, qr);
		merge(ret, vl, vr);
		return ret;
	}
} mincnt;

struct segtree{
	ll seg[4*maxn], tag[4*maxn];
	void init(int cur, int l, int r, ll a[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = a[l];
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, a), init(cur*2+1, m, r, a);
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	void push(int cur, int l, int r) {
		seg[cur] += tag[cur];
		if (r - l > 1) {
			tag[cur*2] += tag[cur];
			tag[cur*2+1] += tag[cur];
		}
		tag[cur] = 0;
	}
	void pull(int cur, int l, int r) {
		int m = (l + r) / 2;
		push(cur*2, l, m), push(cur*2+1, m, r);
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	void modify(int cur, int l, int r, int ql, int qr, ll x) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += x;
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, x);
		modify(cur*2+1, m, r, ql, qr, x);
		pull(cur, l, r);
	}
	int search(int cur, int l, int r, int ql, int qr, bool type, ll t) {
		//type 0: left, 1:right
		push(cur, l, r);
		if (r <= l || ql >= r || qr <= l || seg[cur] < t) return -1;
		if (r - l == 1) return l;
		int m = (l + r) / 2;
		if (type) {
			int vr = search(cur*2+1, m, r, ql, qr, type, t);
			if (vr != -1) return vr;
			return search(cur*2, l, m, ql, qr, type, t);
		} else {
			int vl = search(cur*2, l, m, ql, qr, type, t);
			if (vl != -1) return vl;
			return search(cur*2+1, m, r, ql, qr, type, t);
		}
	}
	ll query(int cur, int l, int r, int x) { //getpnt
		if (r <= l) return 0;
		push(cur, l, r);
		if (r - l == 1) return seg[cur];
		int m = (l + r) / 2;
		if (x < m) return query(cur*2, l, m, x);
		else query(cur*2+1, m, r, x);
	}
	void print(int cur, int l, int r) {
		if (r <= l) return;
		push(cur, l, r);
		if (r - l == 1) {
			debug(seg[cur]);
			return;
		}
		int m = (l + r) / 2;
		print(cur*2, l, m);
		print(cur*2+1, m, r);
	}
} tr, lb, rb; 
struct BIT{
	ll bit[maxn];
	void modify(int ind, ll val) {
		ind++;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	ll query(int ind) {
		ll ret = 0;
		ind++;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
	ll sum(int l, int r) {
		return query(r) - query(l-1);	
	}
} sum;
ll a[maxn];
int main() {
	io
	int n, q;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		sum.modify(i, a[i]);
	}
	bool ini = 1;
	auto check = [&] (int l, int r, ll s) { //stuck in [l, r]
		if (r < l) return;
		if (ini) s = sum.sum(l, r);
	
		if(!((l && s >= a[l-1]) || (r < n - 1 && s >= a[r+1]))) {
			//debug(l, r);
			inter.ins(1, 0, n, {l, r});				
			mincnt.modify(1, 0, n, l, r+1, 1);	
		}
	};
	tr.init(1, 0, n, a);
	mincnt.init(1, 0, n);
	{
		ll pref[maxn];
		for (int i = 0;i < n;i++) {
			pref[i] = a[i] + (i ? pref[i-1] : 0);
			lb.modify(1, 0, n, i, i+1, a[i] - (i ? pref[i-1] : 0));	
			rb.modify(1, 0, n, i, i+1, a[i] + pref[i]);
		}
		
		stack<int> stk;
		for (int i = 0;i < n;i++) {
			while (stk.size() && a[i] >= a[stk.top()]) {
				check(stk.top()+1, i-1, 0);
				stk.pop();	
			}
			if (stk.size()) check(stk.top()+1, i-1, 0);	
			else check(0, i-1, 0);
			stk.push(i);
		}
		while (stk.size()) {
			check(stk.top()+1, n-1, 0);
			stk.pop();
		}
	}
	ini = 0;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int i, y;
			cin >> i >> y;
			i--;
			ll d = y - a[i];
			tr.modify(1, 0, n, i, i+1, d); 
			lb.modify(1, 0, n, i, i+1, d);
			rb.modify(1, 0, n, i, i+1, d);
			lb.modify(1, 0, n, i+1, n, -d);
			rb.modify(1, 0, n, i, n, d);
			sum.modify(i, d);
			a[i] = y;

			vector<pii> rem;
			inter.remove(1, 0, n, i, rem);
			inter.remove(1, 0, n, i-1, rem);
			inter.remove(1, 0, n, i+1, rem);
			for (auto p:rem) {
				//debug("rem", p.ff, p.ss);
				mincnt.modify(1, 0, n, p.ff, p.ss+1, -1);
			}
			vector<int> lef, rig;
			int cur = i+1;		
			ll s = a[i];
			if (i+1 < n) {
				if (a[i+1] < s) s = a[i+1], cur = i+2;
				lef.push_back(i+1);
			}
			while (cur < n) {
				int nxt = tr.search(1, 0, n, cur, n, 0, s+1);
				if (nxt != -1) {
					rig.push_back(nxt-1);
					cur = nxt;
					s += a[nxt];
				} else {
					break;
				}
			}
			rig.push_back(n-1);	
			cur = i-1, s = a[i];	
			if (i-1 >= 0) {
				if (a[i-1] < s) s = a[i-1], cur = i-2;
				rig.insert(rig.begin(), i-1);
			}
			while (cur >= 0) {
				int nxt = tr.search(1, 0, n, 0, cur+1, 1, s+1);
				if (nxt != -1) {
					lef.push_back(nxt+1);
					cur = nxt;
					s += a[nxt];
				} else {
					break;
				}
			}
			lef.push_back(0);

			lef.resize(int(unique(lef.begin(), lef.end()) - lef.begin()));
			rig.resize(int(unique(rig.begin(), rig.end()) - rig.begin()));
			vector<ll> ls, rs;
			for (int I:lef) ls.push_back(sum.query(I-1)); 
			for (int I:rig) rs.push_back(sum.query(I));
			for (int I = 0;I < lef.size();I++) {
				for (int j = 0;j < rig.size();j++) {
					check(lef[I], rig[j], rs[j] - ls[I]);
				}
			}

		} else {
			int l, r;
			cin >> l >> r;
			l--; //[l, r)
			ll suml = -sum.query(l-1)+1, sumr = sum.query(r-1)+1;
			int il = lb.search(1, 0, n, l, r, 1, suml);
			int ir = rb.search(1, 0, n, l, r, 0, sumr)+1;
			if (il != -1) l = il;
			if (ir != -1) r = ir;
			cout << mincnt.query(1, 0, n, l, r).ss << "\n";
		}
	}
}
/*
*/

Compilation message

fish2.cpp: In member function 'void segtree::print(int, int, int)':
fish2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
fish2.cpp:164:4: note: in expansion of macro 'debug'
  164 |    debug(seg[cur]);
      |    ^~~~~
fish2.cpp: In function 'int main()':
fish2.cpp:299:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  299 |    for (int I = 0;I < lef.size();I++) {
      |                   ~~^~~~~~~~~~~~
fish2.cpp:300:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  300 |     for (int j = 0;j < rig.size();j++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 273536 KB Output is correct
2 Correct 161 ms 273592 KB Output is correct
3 Correct 160 ms 273520 KB Output is correct
4 Correct 155 ms 273604 KB Output is correct
5 Correct 159 ms 273664 KB Output is correct
6 Correct 181 ms 273568 KB Output is correct
7 Correct 176 ms 273648 KB Output is correct
8 Correct 156 ms 273672 KB Output is correct
9 Correct 176 ms 273620 KB Output is correct
10 Correct 170 ms 273544 KB Output is correct
11 Correct 158 ms 273780 KB Output is correct
12 Correct 160 ms 273588 KB Output is correct
13 Correct 164 ms 273664 KB Output is correct
14 Correct 163 ms 273676 KB Output is correct
15 Correct 164 ms 273616 KB Output is correct
16 Correct 164 ms 273668 KB Output is correct
17 Correct 159 ms 273664 KB Output is correct
18 Correct 159 ms 273664 KB Output is correct
19 Correct 159 ms 273660 KB Output is correct
20 Correct 164 ms 273580 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 273592 KB Output is correct
2 Correct 265 ms 286332 KB Output is correct
3 Correct 308 ms 286396 KB Output is correct
4 Correct 256 ms 286396 KB Output is correct
5 Correct 261 ms 286440 KB Output is correct
6 Correct 275 ms 286396 KB Output is correct
7 Correct 241 ms 286400 KB Output is correct
8 Correct 274 ms 286396 KB Output is correct
9 Correct 257 ms 286324 KB Output is correct
10 Correct 245 ms 286400 KB Output is correct
11 Correct 253 ms 286292 KB Output is correct
12 Correct 277 ms 286276 KB Output is correct
13 Correct 247 ms 286420 KB Output is correct
14 Correct 273 ms 286392 KB Output is correct
15 Correct 302 ms 286304 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 273536 KB Output is correct
2 Correct 161 ms 273592 KB Output is correct
3 Correct 160 ms 273520 KB Output is correct
4 Correct 155 ms 273604 KB Output is correct
5 Correct 159 ms 273664 KB Output is correct
6 Correct 181 ms 273568 KB Output is correct
7 Correct 176 ms 273648 KB Output is correct
8 Correct 156 ms 273672 KB Output is correct
9 Correct 176 ms 273620 KB Output is correct
10 Correct 170 ms 273544 KB Output is correct
11 Correct 158 ms 273780 KB Output is correct
12 Correct 160 ms 273588 KB Output is correct
13 Correct 164 ms 273664 KB Output is correct
14 Correct 163 ms 273676 KB Output is correct
15 Correct 164 ms 273616 KB Output is correct
16 Correct 164 ms 273668 KB Output is correct
17 Correct 159 ms 273664 KB Output is correct
18 Correct 159 ms 273664 KB Output is correct
19 Correct 159 ms 273660 KB Output is correct
20 Correct 164 ms 273580 KB Output is correct
21 Correct 156 ms 273592 KB Output is correct
22 Correct 265 ms 286332 KB Output is correct
23 Correct 308 ms 286396 KB Output is correct
24 Correct 256 ms 286396 KB Output is correct
25 Correct 261 ms 286440 KB Output is correct
26 Correct 275 ms 286396 KB Output is correct
27 Correct 241 ms 286400 KB Output is correct
28 Correct 274 ms 286396 KB Output is correct
29 Correct 257 ms 286324 KB Output is correct
30 Correct 245 ms 286400 KB Output is correct
31 Correct 253 ms 286292 KB Output is correct
32 Correct 277 ms 286276 KB Output is correct
33 Correct 247 ms 286420 KB Output is correct
34 Correct 273 ms 286392 KB Output is correct
35 Correct 302 ms 286304 KB Output is correct
36 Correct 283 ms 288868 KB Output is correct
37 Correct 275 ms 288244 KB Output is correct
38 Correct 277 ms 287292 KB Output is correct
39 Correct 297 ms 289076 KB Output is correct
40 Correct 297 ms 287588 KB Output is correct
41 Correct 301 ms 288996 KB Output is correct
42 Correct 261 ms 288456 KB Output is correct
43 Correct 259 ms 288516 KB Output is correct
44 Correct 252 ms 288124 KB Output is correct
45 Correct 268 ms 288840 KB Output is correct
46 Correct 264 ms 287008 KB Output is correct
47 Correct 242 ms 286772 KB Output is correct
48 Correct 253 ms 288572 KB Output is correct
49 Correct 262 ms 287820 KB Output is correct
50 Correct 260 ms 288836 KB Output is correct
51 Correct 270 ms 288824 KB Output is correct
52 Correct 298 ms 287764 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 273592 KB Output is correct
2 Correct 265 ms 286332 KB Output is correct
3 Correct 308 ms 286396 KB Output is correct
4 Correct 256 ms 286396 KB Output is correct
5 Correct 261 ms 286440 KB Output is correct
6 Correct 275 ms 286396 KB Output is correct
7 Correct 241 ms 286400 KB Output is correct
8 Correct 274 ms 286396 KB Output is correct
9 Correct 257 ms 286324 KB Output is correct
10 Correct 245 ms 286400 KB Output is correct
11 Correct 253 ms 286292 KB Output is correct
12 Correct 277 ms 286276 KB Output is correct
13 Correct 247 ms 286420 KB Output is correct
14 Correct 273 ms 286392 KB Output is correct
15 Correct 302 ms 286304 KB Output is correct
16 Correct 157 ms 273580 KB Output is correct
17 Correct 390 ms 286760 KB Output is correct
18 Correct 457 ms 286820 KB Output is correct
19 Correct 420 ms 286756 KB Output is correct
20 Correct 435 ms 286660 KB Output is correct
21 Correct 425 ms 286700 KB Output is correct
22 Correct 445 ms 286808 KB Output is correct
23 Correct 449 ms 286824 KB Output is correct
24 Correct 408 ms 286808 KB Output is correct
25 Correct 397 ms 286736 KB Output is correct
26 Correct 437 ms 286868 KB Output is correct
27 Correct 479 ms 286864 KB Output is correct
28 Correct 410 ms 286932 KB Output is correct
29 Correct 483 ms 287020 KB Output is correct
30 Correct 334 ms 286540 KB Output is correct
31 Correct 342 ms 286560 KB Output is correct
32 Correct 365 ms 286608 KB Output is correct
33 Correct 428 ms 286796 KB Output is correct
34 Correct 398 ms 286600 KB Output is correct
35 Correct 350 ms 286668 KB Output is correct
36 Correct 446 ms 286744 KB Output is correct
37 Correct 352 ms 286644 KB Output is correct
38 Correct 355 ms 286612 KB Output is correct
39 Correct 484 ms 286904 KB Output is correct
40 Correct 384 ms 286876 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 273592 KB Output is correct
2 Correct 265 ms 286332 KB Output is correct
3 Correct 308 ms 286396 KB Output is correct
4 Correct 256 ms 286396 KB Output is correct
5 Correct 261 ms 286440 KB Output is correct
6 Correct 275 ms 286396 KB Output is correct
7 Correct 241 ms 286400 KB Output is correct
8 Correct 274 ms 286396 KB Output is correct
9 Correct 257 ms 286324 KB Output is correct
10 Correct 245 ms 286400 KB Output is correct
11 Correct 253 ms 286292 KB Output is correct
12 Correct 277 ms 286276 KB Output is correct
13 Correct 247 ms 286420 KB Output is correct
14 Correct 273 ms 286392 KB Output is correct
15 Correct 302 ms 286304 KB Output is correct
16 Correct 166 ms 273756 KB Output is correct
17 Correct 1903 ms 288504 KB Output is correct
18 Correct 1265 ms 290496 KB Output is correct
19 Correct 1436 ms 290004 KB Output is correct
20 Correct 1035 ms 290616 KB Output is correct
21 Correct 1812 ms 290060 KB Output is correct
22 Correct 1283 ms 290376 KB Output is correct
23 Correct 1620 ms 289812 KB Output is correct
24 Correct 1220 ms 290452 KB Output is correct
25 Correct 1440 ms 289860 KB Output is correct
26 Correct 790 ms 291112 KB Output is correct
27 Correct 880 ms 291172 KB Output is correct
28 Correct 949 ms 290392 KB Output is correct
29 Correct 818 ms 291036 KB Output is correct
30 Correct 948 ms 291056 KB Output is correct
31 Correct 1105 ms 290384 KB Output is correct
32 Correct 1352 ms 290380 KB Output is correct
33 Correct 891 ms 288260 KB Output is correct
34 Correct 1281 ms 290768 KB Output is correct
35 Correct 789 ms 288544 KB Output is correct
36 Correct 1073 ms 290444 KB Output is correct
37 Correct 1054 ms 290076 KB Output is correct
38 Correct 776 ms 290180 KB Output is correct
39 Correct 886 ms 290668 KB Output is correct
40 Correct 694 ms 290724 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 273536 KB Output is correct
2 Correct 161 ms 273592 KB Output is correct
3 Correct 160 ms 273520 KB Output is correct
4 Correct 155 ms 273604 KB Output is correct
5 Correct 159 ms 273664 KB Output is correct
6 Correct 181 ms 273568 KB Output is correct
7 Correct 176 ms 273648 KB Output is correct
8 Correct 156 ms 273672 KB Output is correct
9 Correct 176 ms 273620 KB Output is correct
10 Correct 170 ms 273544 KB Output is correct
11 Correct 158 ms 273780 KB Output is correct
12 Correct 160 ms 273588 KB Output is correct
13 Correct 164 ms 273664 KB Output is correct
14 Correct 163 ms 273676 KB Output is correct
15 Correct 164 ms 273616 KB Output is correct
16 Correct 164 ms 273668 KB Output is correct
17 Correct 159 ms 273664 KB Output is correct
18 Correct 159 ms 273664 KB Output is correct
19 Correct 159 ms 273660 KB Output is correct
20 Correct 164 ms 273580 KB Output is correct
21 Correct 156 ms 273592 KB Output is correct
22 Correct 265 ms 286332 KB Output is correct
23 Correct 308 ms 286396 KB Output is correct
24 Correct 256 ms 286396 KB Output is correct
25 Correct 261 ms 286440 KB Output is correct
26 Correct 275 ms 286396 KB Output is correct
27 Correct 241 ms 286400 KB Output is correct
28 Correct 274 ms 286396 KB Output is correct
29 Correct 257 ms 286324 KB Output is correct
30 Correct 245 ms 286400 KB Output is correct
31 Correct 253 ms 286292 KB Output is correct
32 Correct 277 ms 286276 KB Output is correct
33 Correct 247 ms 286420 KB Output is correct
34 Correct 273 ms 286392 KB Output is correct
35 Correct 302 ms 286304 KB Output is correct
36 Correct 283 ms 288868 KB Output is correct
37 Correct 275 ms 288244 KB Output is correct
38 Correct 277 ms 287292 KB Output is correct
39 Correct 297 ms 289076 KB Output is correct
40 Correct 297 ms 287588 KB Output is correct
41 Correct 301 ms 288996 KB Output is correct
42 Correct 261 ms 288456 KB Output is correct
43 Correct 259 ms 288516 KB Output is correct
44 Correct 252 ms 288124 KB Output is correct
45 Correct 268 ms 288840 KB Output is correct
46 Correct 264 ms 287008 KB Output is correct
47 Correct 242 ms 286772 KB Output is correct
48 Correct 253 ms 288572 KB Output is correct
49 Correct 262 ms 287820 KB Output is correct
50 Correct 260 ms 288836 KB Output is correct
51 Correct 270 ms 288824 KB Output is correct
52 Correct 298 ms 287764 KB Output is correct
53 Correct 157 ms 273580 KB Output is correct
54 Correct 390 ms 286760 KB Output is correct
55 Correct 457 ms 286820 KB Output is correct
56 Correct 420 ms 286756 KB Output is correct
57 Correct 435 ms 286660 KB Output is correct
58 Correct 425 ms 286700 KB Output is correct
59 Correct 445 ms 286808 KB Output is correct
60 Correct 449 ms 286824 KB Output is correct
61 Correct 408 ms 286808 KB Output is correct
62 Correct 397 ms 286736 KB Output is correct
63 Correct 437 ms 286868 KB Output is correct
64 Correct 479 ms 286864 KB Output is correct
65 Correct 410 ms 286932 KB Output is correct
66 Correct 483 ms 287020 KB Output is correct
67 Correct 334 ms 286540 KB Output is correct
68 Correct 342 ms 286560 KB Output is correct
69 Correct 365 ms 286608 KB Output is correct
70 Correct 428 ms 286796 KB Output is correct
71 Correct 398 ms 286600 KB Output is correct
72 Correct 350 ms 286668 KB Output is correct
73 Correct 446 ms 286744 KB Output is correct
74 Correct 352 ms 286644 KB Output is correct
75 Correct 355 ms 286612 KB Output is correct
76 Correct 484 ms 286904 KB Output is correct
77 Correct 384 ms 286876 KB Output is correct
78 Correct 166 ms 273756 KB Output is correct
79 Correct 1903 ms 288504 KB Output is correct
80 Correct 1265 ms 290496 KB Output is correct
81 Correct 1436 ms 290004 KB Output is correct
82 Correct 1035 ms 290616 KB Output is correct
83 Correct 1812 ms 290060 KB Output is correct
84 Correct 1283 ms 290376 KB Output is correct
85 Correct 1620 ms 289812 KB Output is correct
86 Correct 1220 ms 290452 KB Output is correct
87 Correct 1440 ms 289860 KB Output is correct
88 Correct 790 ms 291112 KB Output is correct
89 Correct 880 ms 291172 KB Output is correct
90 Correct 949 ms 290392 KB Output is correct
91 Correct 818 ms 291036 KB Output is correct
92 Correct 948 ms 291056 KB Output is correct
93 Correct 1105 ms 290384 KB Output is correct
94 Correct 1352 ms 290380 KB Output is correct
95 Correct 891 ms 288260 KB Output is correct
96 Correct 1281 ms 290768 KB Output is correct
97 Correct 789 ms 288544 KB Output is correct
98 Correct 1073 ms 290444 KB Output is correct
99 Correct 1054 ms 290076 KB Output is correct
100 Correct 776 ms 290180 KB Output is correct
101 Correct 886 ms 290668 KB Output is correct
102 Correct 694 ms 290724 KB Output is correct
103 Correct 1735 ms 289756 KB Output is correct
104 Correct 1348 ms 290860 KB Output is correct
105 Correct 620 ms 290328 KB Output is correct
106 Correct 591 ms 290496 KB Output is correct
107 Correct 1686 ms 289900 KB Output is correct
108 Correct 1280 ms 290664 KB Output is correct
109 Correct 846 ms 290292 KB Output is correct
110 Correct 829 ms 290580 KB Output is correct
111 Correct 608 ms 290272 KB Output is correct
112 Correct 722 ms 290556 KB Output is correct
113 Correct 911 ms 291324 KB Output is correct
114 Correct 480 ms 291296 KB Output is correct
115 Correct 1073 ms 290400 KB Output is correct
116 Correct 879 ms 290460 KB Output is correct
117 Correct 525 ms 291412 KB Output is correct
118 Correct 566 ms 290348 KB Output is correct
119 Correct 917 ms 291048 KB Output is correct
120 Correct 1006 ms 290428 KB Output is correct
121 Correct 767 ms 290376 KB Output is correct
122 Correct 1245 ms 290368 KB Output is correct
123 Correct 728 ms 288200 KB Output is correct
124 Correct 699 ms 290456 KB Output is correct
125 Correct 455 ms 288456 KB Output is correct
126 Correct 637 ms 290468 KB Output is correct
127 Correct 1069 ms 290316 KB Output is correct
128 Correct 494 ms 290332 KB Output is correct
129 Correct 863 ms 290800 KB Output is correct
130 Correct 593 ms 290968 KB Output is correct