oj.uz

Submission #953019

# Submission time Handle Problem Language Result Execution time Memory
953019 2024-03-25T10:19:31 Z WonderfulWhale Food Court (JOI21_foodcourt) C++17
100 / 100
 939 ms 176532 KB 
// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
using namespace std;

#define INT __int128
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll __int128

const int INF = 1e17;

const int MAXN = 250'009;

namespace special {

const int MAXN = 500001;  // 1-based

int N = 400000;
ll A[MAXN];


struct Node {
	ll sum;   // Sum tag
	ll max1;  // Max value
	ll max2;  // Second Max value
	ll maxc;  // Max value count
	ll min1;  // Min value
	ll min2;  // Second Min value
	ll minc;  // Min value count
	ll lazy;  // Lazy tag
} T[MAXN * 4];

void merge(int t) {
	// sum
	T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;
	// cerr << "check: " << (int)T[t].sum << "\n";

	// max
	if (T[t << 1].max1 == T[t << 1 | 1].max1) {
		T[t].max1 = T[t << 1].max1;
		T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
		T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
	} else {
		if (T[t << 1].max1 > T[t << 1 | 1].max1) {
			T[t].max1 = T[t << 1].max1;
			T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
			T[t].maxc = T[t << 1].maxc;
		} else {
			T[t].max1 = T[t << 1 | 1].max1;
			T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
			T[t].maxc = T[t << 1 | 1].maxc;
		}
	}

	// min
	if (T[t << 1].min1 == T[t << 1 | 1].min1) {
		T[t].min1 = T[t << 1].min1;
		T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
		T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
	} else {
		if (T[t << 1].min1 < T[t << 1 | 1].min1) {
			T[t].min1 = T[t << 1].min1;
			T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
			T[t].minc = T[t << 1].minc;
		} else {
			T[t].min1 = T[t << 1 | 1].min1;
			T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
			T[t].minc = T[t << 1 | 1].minc;
		}
	}
}

void push_add(int t, int tl, int tr, ll v) {
	if (v == 0) { return; }
	T[t].sum += (tr - tl + 1) * v;
	T[t].max1 += v;
	if (T[t].max2 != -INF) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != INF) { T[t].min2 += v; }
	T[t].lazy += v;
}

// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
	if (v <= T[t].min1) { return; }
	T[t].sum -= T[t].min1 * T[t].minc;
	T[t].min1 = v;
	T[t].sum += T[t].min1 * T[t].minc;
	if (l) {
		T[t].max1 = T[t].min1;
	} else {
		if (v >= T[t].max1) {
			T[t].max1 = v;
		} else if (v > T[t].max2) {
			T[t].max2 = v;
		}
	}
}

void pushdown(int t, int tl, int tr) {
	if (tl == tr) return;
	// sum
	int tm = (tl + tr) >> 1;
	push_add(t << 1, tl, tm, T[t].lazy);
	push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
	T[t].lazy = 0;

	// min
	push_min(t << 1, T[t].min1, tl == tm);
	push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}

void build(int t = 1, int tl = 0, int tr = N - 1) {
	T[t].lazy = 0;
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -INF;
		T[t].min2 = INF;
		return;
	}

	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_add(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	// cerr << "change!!!\n";
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		push_add(t, tl, tr, v);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_add(l, r, v, t << 1, tl, tm);
	update_add(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v <= T[t].min1) { return; }
	if (l <= tl && tr <= r && v < T[t].min2) {
		push_min(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_chmax(l, r, v, t << 1, tl, tm);
	update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return T[t].sum; }
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	return query_sum(l, r, t << 1, tl, tm) +
	       query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
}

struct SegTree {
	const static int T = 1<<20;
	int t[2*T];
	void update(int l, int r, int val) {
		// cerr << "we are for sure doing something\n";
		// cerr << "dane: "<< l << " " << r<< "\n";
		// cerr << val << "!!!\n";
		l+=T, r+=T;
		t[l]+=val;
		// cerr << "update: " << l << "\n";
		if(l!=r) {
			t[r]+=val;
			// cerr << "update: " << r << "\n";
		}
		// cerr << "start: "<< l << " " << r << "\n";
		while(l/2!=r/2) {
			// cerr << "i cyk\n";
			if(l%2==0) {
				t[l+1]+=val;
				// cerr << "update: " << l+1 << "\n";
			}
			if(r%2==1) {
				t[r-1]+=val;
				// cerr << "update: " << r-1 << "\n";
			}
			l/=2;
			r/=2;
			// cerr << "new: " << l << " " << r << "\n";
			// cerr << "polowki: " << l/2 << " " << r/2 << "\n";
		}
	}
	int query(int x) {
		// cerr << "query: " << x << "\n";
		x+=T;
		int ret = 0;
		while(x){ 
			// cerr << t[x] << " " << x <<" WOW\n";
			ret += t[x];
			x/=2;
		}
		return ret;
	}
} seg;

struct SegTree2 {
	const static int T = 1<<18;
	pii t[2*T];
	int lz[2*T];
	SegTree2() {
		for(int i=T;i<2*T;i++) {
			t[i] = {INF, i-T};
		}
		for(int i=T-1;i;i--) {
			t[i] = min(t[2*i], t[2*i+1]);
		}
	}
	void push(int v) {
		int l = 2*v, r = 2*v+1;
		t[l].st += lz[v];
		t[r].st += lz[v];
		lz[l] += lz[v];
		lz[r] += lz[v];
		lz[v] = 0;
	}
	void update(int l, int r, int val, int tl=0, int tr=T-1, int v=1) {
		// if(v==1) cerr << "update: " << l << " " << r << " " << val << "\n";
		if(l>r) return;
		if(l==tl&&r==tr) {
			t[v].st += val;
			lz[v] += val;
			return;
		}
		push(v);
		int tm = (tl+tr)/2;
		update(l, min(r, tm), val, tl, tm, 2*v);
		update(max(tm+1, l), r, val, tm+1, tr, 2*v+1);
		t[v] = min(t[2*v], t[2*v+1]);
	}
	pii query(int l, int r, int tl=0, int tr=T-1, int v=1) {
		if(l>r) return make_pair(INF, -1);
		if(l==tl&&r==tr) {
			return t[v];
		}
		push(v);
		int tm = (tl+tr)/2;
		return min(query(l, min(r, tm), tl, tm, 2*v),
				query(max(tm+1, l), r, tm+1, tr, 2*v+1));
	}
} seg2;

vector<tuple<int, int, int, int>> Q;
int tab[MAXN];
int lim[MAXN];
pii info[MAXN];
int ans[MAXN];

int tmp[MAXN];
int del[MAXN];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	vector<pii> zap;
	
	int n, m, q;
	cin >> n >> m >> q;
	int cnt = 0;
	int cnt3 = 0;
	special::build();
	for(int i=0;i<q;i++) {
		int type;
		cin >> type;
		if(type==1) {
			int l, r, c, k;
			cin >> l >> r >> k >> c;
			tab[cnt] = k;
			Q.pb({l, r, c, k});
			cnt++;
			seg.update(l, r, c);
			// cerr << "update: " << l << " " << r << " " << c << "\n";
			special::update_add(l, r, c);
			// cerr << "CHANGE \n";
			// cerr << l << " " << r << " " << c << " " << special::query_sum(0, 1000) << "\n";
			// for(int i=l;i<=r;i++) {
			// 	tmp[i] += c;
			// }
		}
		if(type==2) {
			int l, r, c;
			cin >> l >> r >> c;
			// seg.update(l, r, c);
			special::update_add(l, r, -c);
			special::update_chmax(l, r, 0);
			// for(int i=l;i<=r;i++) {
			// 	int val = min(c, tmp[i]);
			// 	tmp[i] -= val;
			// 	del[i] += val;
			// }
		}
		if(type==3) {
			int a, b;
			cin >> a >> b;
			// cerr << "QUERY : "<< a << "\n";
			// cerr << "query: " << a << " " << b << "\n";
			// b += seg.query(a);
			// cerr << "check: " << seg.query(a) << "\n";
			// cerr << "check2: " << (int)(special::query_sum(a, a)/INF) << (int)(special::query_sum(a, a)%INF) << "\n";
			int diff = seg.query(a)-special::query_sum(a, a);
			// b += del[a];
			b += diff;
			// cerr << del[a] << " " << diff << " test\n";
			// cerr << "we need: " << b << "\n";
			// cerr << "we can process: " << cnt << "\n";
			info[cnt3] = {cnt, b};
			zap.pb({a, cnt3++});
		}
	}
	// cerr << seg.query(106761) << " HAHA\n";
	sort(all(zap));
	for(int i=0;i<cnt3;i++) {
		int num = zap[i].nd;
		// cerr << "hm: " << info[num].nd << "\n";
		seg2.update(i, i, -INF+info[num].nd);
		pii X = seg2.query(i, i);
		// cerr << "just a quick check: " << X.st << " " << X.nd << "\n";
	}
	for(int i=0;i<cnt;i++) {
		auto [l, r, C, k] = Q[i];
		// cerr << "Now adding: " << l << " " << r << " " << C << " " << k << "\n";
		int s = -1;
		int e = cnt3;
		while(e-s>1) {
			int m = (e+s)/2;
			if(zap[m].st>=l) e = m;
			else s = m;
		}
		int S = e;
		s = -1, e = cnt3;
		while(e-s>1) {
			int m = (e+s)/2;
			if(zap[m].st<=r) s = m;
			else e = m;
		}
		int E = s;
		// cerr << "we will affect queries: "<< S << " " << E << "\n";
		seg2.update(S, E, -C);
		while(true) {
			pii x = seg2.query(0, cnt3-1);
			if(x.st>0) break;
			// cerr << "found: " << x.nd << " with new val: " << x.st << "\n";
			if(i<info[zap[x.nd].nd].st) ans[zap[x.nd].nd] = tab[i];
			seg2.update(x.nd, x.nd, INF);
		}
	}
	for(int i=0;i<cnt3;i++) {
		cout << ans[i] << "\n";
	}
}

Compilation message

foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:338:7: warning: variable 'X' set but not used [-Wunused-but-set-variable]
  338 |   pii X = seg2.query(i, i);
      |       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 150328 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150580 KB Output is correct
4 Correct 31 ms 150356 KB Output is correct
5 Correct 29 ms 150260 KB Output is correct
6 Correct 27 ms 150356 KB Output is correct
7 Correct 27 ms 150360 KB Output is correct
8 Correct 30 ms 150356 KB Output is correct
9 Correct 34 ms 150652 KB Output is correct
10 Correct 32 ms 150356 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 152408 KB Output is correct
13 Correct 27 ms 150364 KB Output is correct
14 Correct 28 ms 150356 KB Output is correct
15 Correct 27 ms 150352 KB Output is correct
16 Correct 27 ms 150364 KB Output is correct
17 Correct 28 ms 150404 KB Output is correct
18 Correct 29 ms 150356 KB Output is correct
19 Correct 28 ms 150356 KB Output is correct
20 Correct 28 ms 150352 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 150328 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150580 KB Output is correct
4 Correct 31 ms 150356 KB Output is correct
5 Correct 29 ms 150260 KB Output is correct
6 Correct 27 ms 150356 KB Output is correct
7 Correct 27 ms 150360 KB Output is correct
8 Correct 30 ms 150356 KB Output is correct
9 Correct 34 ms 150652 KB Output is correct
10 Correct 32 ms 150356 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 152408 KB Output is correct
13 Correct 27 ms 150364 KB Output is correct
14 Correct 28 ms 150356 KB Output is correct
15 Correct 27 ms 150352 KB Output is correct
16 Correct 27 ms 150364 KB Output is correct
17 Correct 28 ms 150404 KB Output is correct
18 Correct 29 ms 150356 KB Output is correct
19 Correct 28 ms 150356 KB Output is correct
20 Correct 28 ms 150352 KB Output is correct
21 Correct 28 ms 148560 KB Output is correct
22 Correct 29 ms 146360 KB Output is correct
23 Correct 27 ms 148304 KB Output is correct
24 Correct 28 ms 146264 KB Output is correct
25 Correct 26 ms 146268 KB Output is correct
26 Correct 26 ms 146176 KB Output is correct
27 Correct 29 ms 146172 KB Output is correct
28 Correct 27 ms 146388 KB Output is correct
29 Correct 28 ms 146388 KB Output is correct
30 Correct 28 ms 146268 KB Output is correct
31 Correct 29 ms 146264 KB Output is correct
32 Correct 29 ms 146288 KB Output is correct
33 Correct 27 ms 148316 KB Output is correct
34 Correct 27 ms 146376 KB Output is correct
35 Correct 30 ms 148304 KB Output is correct
36 Correct 29 ms 148316 KB Output is correct
37 Correct 27 ms 148292 KB Output is correct
38 Correct 26 ms 146268 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 151672 KB Output is correct
2 Correct 201 ms 150020 KB Output is correct
3 Correct 193 ms 150232 KB Output is correct
4 Correct 176 ms 149736 KB Output is correct
5 Correct 178 ms 150092 KB Output is correct
6 Correct 189 ms 150184 KB Output is correct
7 Correct 98 ms 149008 KB Output is correct
8 Correct 93 ms 148428 KB Output is correct
9 Correct 162 ms 150080 KB Output is correct
10 Correct 177 ms 151684 KB Output is correct
11 Correct 175 ms 151372 KB Output is correct
12 Correct 214 ms 160584 KB Output is correct
13 Correct 152 ms 160996 KB Output is correct
14 Correct 170 ms 155972 KB Output is correct
15 Correct 150 ms 161408 KB Output is correct
16 Correct 171 ms 156464 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 165184 KB Output is correct
2 Correct 658 ms 164192 KB Output is correct
3 Correct 820 ms 166568 KB Output is correct
4 Correct 595 ms 174412 KB Output is correct
5 Correct 577 ms 171704 KB Output is correct
6 Correct 809 ms 172988 KB Output is correct
7 Correct 305 ms 163136 KB Output is correct
8 Correct 284 ms 164788 KB Output is correct
9 Correct 844 ms 167836 KB Output is correct
10 Correct 800 ms 173064 KB Output is correct
11 Correct 805 ms 173004 KB Output is correct
12 Correct 775 ms 172296 KB Output is correct
13 Correct 779 ms 174992 KB Output is correct
14 Correct 901 ms 173824 KB Output is correct
15 Correct 887 ms 169704 KB Output is correct
16 Correct 895 ms 167864 KB Output is correct
17 Correct 887 ms 174924 KB Output is correct
18 Correct 829 ms 174880 KB Output is correct
19 Correct 863 ms 175212 KB Output is correct
20 Correct 867 ms 174972 KB Output is correct
21 Correct 939 ms 175392 KB Output is correct
22 Correct 909 ms 174992 KB Output is correct
23 Correct 845 ms 169772 KB Output is correct
24 Correct 883 ms 169820 KB Output is correct
25 Correct 608 ms 162024 KB Output is correct
26 Correct 565 ms 164376 KB Output is correct
27 Correct 619 ms 171096 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 150328 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150580 KB Output is correct
4 Correct 31 ms 150356 KB Output is correct
5 Correct 29 ms 150260 KB Output is correct
6 Correct 27 ms 150356 KB Output is correct
7 Correct 27 ms 150360 KB Output is correct
8 Correct 30 ms 150356 KB Output is correct
9 Correct 34 ms 150652 KB Output is correct
10 Correct 32 ms 150356 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 152408 KB Output is correct
13 Correct 27 ms 150364 KB Output is correct
14 Correct 28 ms 150356 KB Output is correct
15 Correct 27 ms 150352 KB Output is correct
16 Correct 27 ms 150364 KB Output is correct
17 Correct 28 ms 150404 KB Output is correct
18 Correct 29 ms 150356 KB Output is correct
19 Correct 28 ms 150356 KB Output is correct
20 Correct 28 ms 150352 KB Output is correct
21 Correct 176 ms 151672 KB Output is correct
22 Correct 201 ms 150020 KB Output is correct
23 Correct 193 ms 150232 KB Output is correct
24 Correct 176 ms 149736 KB Output is correct
25 Correct 178 ms 150092 KB Output is correct
26 Correct 189 ms 150184 KB Output is correct
27 Correct 98 ms 149008 KB Output is correct
28 Correct 93 ms 148428 KB Output is correct
29 Correct 162 ms 150080 KB Output is correct
30 Correct 177 ms 151684 KB Output is correct
31 Correct 175 ms 151372 KB Output is correct
32 Correct 214 ms 160584 KB Output is correct
33 Correct 152 ms 160996 KB Output is correct
34 Correct 170 ms 155972 KB Output is correct
35 Correct 150 ms 161408 KB Output is correct
36 Correct 171 ms 156464 KB Output is correct
37 Correct 194 ms 162240 KB Output is correct
38 Correct 144 ms 162320 KB Output is correct
39 Correct 73 ms 153932 KB Output is correct
40 Correct 82 ms 156196 KB Output is correct
41 Correct 175 ms 154980 KB Output is correct
42 Correct 174 ms 162568 KB Output is correct
43 Correct 207 ms 162828 KB Output is correct
44 Correct 192 ms 160752 KB Output is correct
45 Correct 171 ms 162572 KB Output is correct
46 Correct 228 ms 162668 KB Output is correct
47 Correct 115 ms 154292 KB Output is correct
48 Correct 146 ms 154304 KB Output is correct
49 Correct 161 ms 162412 KB Output is correct
50 Correct 191 ms 155184 KB Output is correct
51 Correct 221 ms 162636 KB Output is correct
52 Correct 238 ms 155420 KB Output is correct
53 Correct 126 ms 160744 KB Output is correct
54 Correct 163 ms 161588 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 157016 KB Output is correct
2 Correct 174 ms 156892 KB Output is correct
3 Correct 174 ms 164492 KB Output is correct
4 Correct 134 ms 154596 KB Output is correct
5 Correct 163 ms 155056 KB Output is correct
6 Correct 182 ms 157268 KB Output is correct
7 Correct 90 ms 157816 KB Output is correct
8 Correct 87 ms 153820 KB Output is correct
9 Correct 144 ms 164392 KB Output is correct
10 Correct 113 ms 162864 KB Output is correct
11 Correct 157 ms 163140 KB Output is correct
12 Correct 166 ms 165692 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 150328 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150580 KB Output is correct
4 Correct 31 ms 150356 KB Output is correct
5 Correct 29 ms 150260 KB Output is correct
6 Correct 27 ms 150356 KB Output is correct
7 Correct 27 ms 150360 KB Output is correct
8 Correct 30 ms 150356 KB Output is correct
9 Correct 34 ms 150652 KB Output is correct
10 Correct 32 ms 150356 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 152408 KB Output is correct
13 Correct 27 ms 150364 KB Output is correct
14 Correct 28 ms 150356 KB Output is correct
15 Correct 27 ms 150352 KB Output is correct
16 Correct 27 ms 150364 KB Output is correct
17 Correct 28 ms 150404 KB Output is correct
18 Correct 29 ms 150356 KB Output is correct
19 Correct 28 ms 150356 KB Output is correct
20 Correct 28 ms 150352 KB Output is correct
21 Correct 28 ms 148560 KB Output is correct
22 Correct 29 ms 146360 KB Output is correct
23 Correct 27 ms 148304 KB Output is correct
24 Correct 28 ms 146264 KB Output is correct
25 Correct 26 ms 146268 KB Output is correct
26 Correct 26 ms 146176 KB Output is correct
27 Correct 29 ms 146172 KB Output is correct
28 Correct 27 ms 146388 KB Output is correct
29 Correct 28 ms 146388 KB Output is correct
30 Correct 28 ms 146268 KB Output is correct
31 Correct 29 ms 146264 KB Output is correct
32 Correct 29 ms 146288 KB Output is correct
33 Correct 27 ms 148316 KB Output is correct
34 Correct 27 ms 146376 KB Output is correct
35 Correct 30 ms 148304 KB Output is correct
36 Correct 29 ms 148316 KB Output is correct
37 Correct 27 ms 148292 KB Output is correct
38 Correct 26 ms 146268 KB Output is correct
39 Correct 176 ms 151672 KB Output is correct
40 Correct 201 ms 150020 KB Output is correct
41 Correct 193 ms 150232 KB Output is correct
42 Correct 176 ms 149736 KB Output is correct
43 Correct 178 ms 150092 KB Output is correct
44 Correct 189 ms 150184 KB Output is correct
45 Correct 98 ms 149008 KB Output is correct
46 Correct 93 ms 148428 KB Output is correct
47 Correct 162 ms 150080 KB Output is correct
48 Correct 177 ms 151684 KB Output is correct
49 Correct 175 ms 151372 KB Output is correct
50 Correct 214 ms 160584 KB Output is correct
51 Correct 152 ms 160996 KB Output is correct
52 Correct 170 ms 155972 KB Output is correct
53 Correct 150 ms 161408 KB Output is correct
54 Correct 171 ms 156464 KB Output is correct
55 Correct 194 ms 162240 KB Output is correct
56 Correct 144 ms 162320 KB Output is correct
57 Correct 73 ms 153932 KB Output is correct
58 Correct 82 ms 156196 KB Output is correct
59 Correct 175 ms 154980 KB Output is correct
60 Correct 174 ms 162568 KB Output is correct
61 Correct 207 ms 162828 KB Output is correct
62 Correct 192 ms 160752 KB Output is correct
63 Correct 171 ms 162572 KB Output is correct
64 Correct 228 ms 162668 KB Output is correct
65 Correct 115 ms 154292 KB Output is correct
66 Correct 146 ms 154304 KB Output is correct
67 Correct 161 ms 162412 KB Output is correct
68 Correct 191 ms 155184 KB Output is correct
69 Correct 221 ms 162636 KB Output is correct
70 Correct 238 ms 155420 KB Output is correct
71 Correct 126 ms 160744 KB Output is correct
72 Correct 163 ms 161588 KB Output is correct
73 Correct 159 ms 157016 KB Output is correct
74 Correct 174 ms 156892 KB Output is correct
75 Correct 174 ms 164492 KB Output is correct
76 Correct 134 ms 154596 KB Output is correct
77 Correct 163 ms 155056 KB Output is correct
78 Correct 182 ms 157268 KB Output is correct
79 Correct 90 ms 157816 KB Output is correct
80 Correct 87 ms 153820 KB Output is correct
81 Correct 144 ms 164392 KB Output is correct
82 Correct 113 ms 162864 KB Output is correct
83 Correct 157 ms 163140 KB Output is correct
84 Correct 166 ms 165692 KB Output is correct
85 Correct 175 ms 162628 KB Output is correct
86 Correct 182 ms 155844 KB Output is correct
87 Correct 155 ms 163140 KB Output is correct
88 Correct 178 ms 161292 KB Output is correct
89 Correct 127 ms 162080 KB Output is correct
90 Correct 165 ms 162828 KB Output is correct
91 Correct 162 ms 155208 KB Output is correct
92 Correct 180 ms 162368 KB Output is correct
93 Correct 181 ms 162884 KB Output is correct
94 Correct 170 ms 156044 KB Output is correct
95 Correct 166 ms 155468 KB Output is correct
96 Correct 183 ms 162836 KB Output is correct
97 Correct 227 ms 161020 KB Output is correct
98 Correct 161 ms 160812 KB Output is correct
99 Correct 128 ms 162976 KB Output is correct
100 Correct 132 ms 154696 KB Output is correct
101 Correct 156 ms 162752 KB Output is correct
102 Correct 146 ms 161480 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 150328 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150580 KB Output is correct
4 Correct 31 ms 150356 KB Output is correct
5 Correct 29 ms 150260 KB Output is correct
6 Correct 27 ms 150356 KB Output is correct
7 Correct 27 ms 150360 KB Output is correct
8 Correct 30 ms 150356 KB Output is correct
9 Correct 34 ms 150652 KB Output is correct
10 Correct 32 ms 150356 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 152408 KB Output is correct
13 Correct 27 ms 150364 KB Output is correct
14 Correct 28 ms 150356 KB Output is correct
15 Correct 27 ms 150352 KB Output is correct
16 Correct 27 ms 150364 KB Output is correct
17 Correct 28 ms 150404 KB Output is correct
18 Correct 29 ms 150356 KB Output is correct
19 Correct 28 ms 150356 KB Output is correct
20 Correct 28 ms 150352 KB Output is correct
21 Correct 28 ms 148560 KB Output is correct
22 Correct 29 ms 146360 KB Output is correct
23 Correct 27 ms 148304 KB Output is correct
24 Correct 28 ms 146264 KB Output is correct
25 Correct 26 ms 146268 KB Output is correct
26 Correct 26 ms 146176 KB Output is correct
27 Correct 29 ms 146172 KB Output is correct
28 Correct 27 ms 146388 KB Output is correct
29 Correct 28 ms 146388 KB Output is correct
30 Correct 28 ms 146268 KB Output is correct
31 Correct 29 ms 146264 KB Output is correct
32 Correct 29 ms 146288 KB Output is correct
33 Correct 27 ms 148316 KB Output is correct
34 Correct 27 ms 146376 KB Output is correct
35 Correct 30 ms 148304 KB Output is correct
36 Correct 29 ms 148316 KB Output is correct
37 Correct 27 ms 148292 KB Output is correct
38 Correct 26 ms 146268 KB Output is correct
39 Correct 176 ms 151672 KB Output is correct
40 Correct 201 ms 150020 KB Output is correct
41 Correct 193 ms 150232 KB Output is correct
42 Correct 176 ms 149736 KB Output is correct
43 Correct 178 ms 150092 KB Output is correct
44 Correct 189 ms 150184 KB Output is correct
45 Correct 98 ms 149008 KB Output is correct
46 Correct 93 ms 148428 KB Output is correct
47 Correct 162 ms 150080 KB Output is correct
48 Correct 177 ms 151684 KB Output is correct
49 Correct 175 ms 151372 KB Output is correct
50 Correct 214 ms 160584 KB Output is correct
51 Correct 152 ms 160996 KB Output is correct
52 Correct 170 ms 155972 KB Output is correct
53 Correct 150 ms 161408 KB Output is correct
54 Correct 171 ms 156464 KB Output is correct
55 Correct 779 ms 165184 KB Output is correct
56 Correct 658 ms 164192 KB Output is correct
57 Correct 820 ms 166568 KB Output is correct
58 Correct 595 ms 174412 KB Output is correct
59 Correct 577 ms 171704 KB Output is correct
60 Correct 809 ms 172988 KB Output is correct
61 Correct 305 ms 163136 KB Output is correct
62 Correct 284 ms 164788 KB Output is correct
63 Correct 844 ms 167836 KB Output is correct
64 Correct 800 ms 173064 KB Output is correct
65 Correct 805 ms 173004 KB Output is correct
66 Correct 775 ms 172296 KB Output is correct
67 Correct 779 ms 174992 KB Output is correct
68 Correct 901 ms 173824 KB Output is correct
69 Correct 887 ms 169704 KB Output is correct
70 Correct 895 ms 167864 KB Output is correct
71 Correct 887 ms 174924 KB Output is correct
72 Correct 829 ms 174880 KB Output is correct
73 Correct 863 ms 175212 KB Output is correct
74 Correct 867 ms 174972 KB Output is correct
75 Correct 939 ms 175392 KB Output is correct
76 Correct 909 ms 174992 KB Output is correct
77 Correct 845 ms 169772 KB Output is correct
78 Correct 883 ms 169820 KB Output is correct
79 Correct 608 ms 162024 KB Output is correct
80 Correct 565 ms 164376 KB Output is correct
81 Correct 619 ms 171096 KB Output is correct
82 Correct 194 ms 162240 KB Output is correct
83 Correct 144 ms 162320 KB Output is correct
84 Correct 73 ms 153932 KB Output is correct
85 Correct 82 ms 156196 KB Output is correct
86 Correct 175 ms 154980 KB Output is correct
87 Correct 174 ms 162568 KB Output is correct
88 Correct 207 ms 162828 KB Output is correct
89 Correct 192 ms 160752 KB Output is correct
90 Correct 171 ms 162572 KB Output is correct
91 Correct 228 ms 162668 KB Output is correct
92 Correct 115 ms 154292 KB Output is correct
93 Correct 146 ms 154304 KB Output is correct
94 Correct 161 ms 162412 KB Output is correct
95 Correct 191 ms 155184 KB Output is correct
96 Correct 221 ms 162636 KB Output is correct
97 Correct 238 ms 155420 KB Output is correct
98 Correct 126 ms 160744 KB Output is correct
99 Correct 163 ms 161588 KB Output is correct
100 Correct 159 ms 157016 KB Output is correct
101 Correct 174 ms 156892 KB Output is correct
102 Correct 174 ms 164492 KB Output is correct
103 Correct 134 ms 154596 KB Output is correct
104 Correct 163 ms 155056 KB Output is correct
105 Correct 182 ms 157268 KB Output is correct
106 Correct 90 ms 157816 KB Output is correct
107 Correct 87 ms 153820 KB Output is correct
108 Correct 144 ms 164392 KB Output is correct
109 Correct 113 ms 162864 KB Output is correct
110 Correct 157 ms 163140 KB Output is correct
111 Correct 166 ms 165692 KB Output is correct
112 Correct 175 ms 162628 KB Output is correct
113 Correct 182 ms 155844 KB Output is correct
114 Correct 155 ms 163140 KB Output is correct
115 Correct 178 ms 161292 KB Output is correct
116 Correct 127 ms 162080 KB Output is correct
117 Correct 165 ms 162828 KB Output is correct
118 Correct 162 ms 155208 KB Output is correct
119 Correct 180 ms 162368 KB Output is correct
120 Correct 181 ms 162884 KB Output is correct
121 Correct 170 ms 156044 KB Output is correct
122 Correct 166 ms 155468 KB Output is correct
123 Correct 183 ms 162836 KB Output is correct
124 Correct 227 ms 161020 KB Output is correct
125 Correct 161 ms 160812 KB Output is correct
126 Correct 128 ms 162976 KB Output is correct
127 Correct 132 ms 154696 KB Output is correct
128 Correct 156 ms 162752 KB Output is correct
129 Correct 146 ms 161480 KB Output is correct
130 Correct 811 ms 172832 KB Output is correct
131 Correct 605 ms 165508 KB Output is correct
132 Correct 922 ms 168460 KB Output is correct
133 Correct 759 ms 176340 KB Output is correct
134 Correct 694 ms 168080 KB Output is correct
135 Correct 794 ms 170968 KB Output is correct
136 Correct 820 ms 173164 KB Output is correct
137 Correct 823 ms 172380 KB Output is correct
138 Correct 788 ms 174104 KB Output is correct
139 Correct 838 ms 176532 KB Output is correct
140 Correct 873 ms 175504 KB Output is correct
141 Correct 811 ms 170232 KB Output is correct
142 Correct 835 ms 175484 KB Output is correct
143 Correct 885 ms 168100 KB Output is correct
144 Correct 788 ms 167224 KB Output is correct
145 Correct 820 ms 175760 KB Output is correct
146 Correct 878 ms 169956 KB Output is correct
147 Correct 916 ms 175468 KB Output is correct
148 Correct 914 ms 170232 KB Output is correct
149 Correct 882 ms 174920 KB Output is correct
150 Correct 487 ms 173644 KB Output is correct
151 Correct 608 ms 174764 KB Output is correct
152 Correct 591 ms 174396 KB Output is correct
153 Correct 603 ms 174512 KB Output is correct