oj.uz

Submission #953017

# Submission time Handle Problem Language Result Execution time Memory
953017 2024-03-25T10:18:38 Z WonderfulWhale Food Court (JOI21_foodcourt) C++17
14 / 100
 1000 ms 155736 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 63 ms 143440 KB Output is correct
2 Correct 47 ms 143336 KB Output is correct
3 Correct 44 ms 143452 KB Output is correct
4 Correct 45 ms 143308 KB Output is correct
5 Correct 40 ms 143392 KB Output is correct
6 Correct 41 ms 143448 KB Output is correct
7 Correct 44 ms 143444 KB Output is correct
8 Correct 44 ms 143504 KB Output is correct
9 Correct 43 ms 143452 KB Output is correct
10 Correct 50 ms 143456 KB Output is correct
11 Correct 50 ms 143440 KB Output is correct
12 Correct 43 ms 143444 KB Output is correct
13 Correct 42 ms 143404 KB Output is correct
14 Correct 45 ms 143444 KB Output is correct
15 Correct 41 ms 143444 KB Output is correct
16 Correct 43 ms 143440 KB Output is correct
17 Correct 42 ms 143440 KB Output is correct
18 Correct 44 ms 143444 KB Output is correct
19 Correct 41 ms 143480 KB Output is correct
20 Correct 46 ms 143436 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 143440 KB Output is correct
2 Correct 47 ms 143336 KB Output is correct
3 Correct 44 ms 143452 KB Output is correct
4 Correct 45 ms 143308 KB Output is correct
5 Correct 40 ms 143392 KB Output is correct
6 Correct 41 ms 143448 KB Output is correct
7 Correct 44 ms 143444 KB Output is correct
8 Correct 44 ms 143504 KB Output is correct
9 Correct 43 ms 143452 KB Output is correct
10 Correct 50 ms 143456 KB Output is correct
11 Correct 50 ms 143440 KB Output is correct
12 Correct 43 ms 143444 KB Output is correct
13 Correct 42 ms 143404 KB Output is correct
14 Correct 45 ms 143444 KB Output is correct
15 Correct 41 ms 143444 KB Output is correct
16 Correct 43 ms 143440 KB Output is correct
17 Correct 42 ms 143440 KB Output is correct
18 Correct 44 ms 143444 KB Output is correct
19 Correct 41 ms 143480 KB Output is correct
20 Correct 46 ms 143436 KB Output is correct
21 Correct 43 ms 143444 KB Output is correct
22 Correct 43 ms 143448 KB Output is correct
23 Correct 44 ms 143408 KB Output is correct
24 Correct 42 ms 143444 KB Output is correct
25 Correct 47 ms 143188 KB Output is correct
26 Correct 40 ms 143184 KB Output is correct
27 Correct 43 ms 143440 KB Output is correct
28 Correct 43 ms 143336 KB Output is correct
29 Correct 45 ms 143460 KB Output is correct
30 Correct 43 ms 143308 KB Output is correct
31 Correct 44 ms 143452 KB Output is correct
32 Correct 45 ms 143484 KB Output is correct
33 Correct 42 ms 143444 KB Output is correct
34 Correct 43 ms 143444 KB Output is correct
35 Correct 44 ms 143380 KB Output is correct
36 Correct 44 ms 143444 KB Output is correct
37 Correct 40 ms 143444 KB Output is correct
38 Correct 44 ms 143368 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 147428 KB Output is correct
2 Correct 500 ms 147464 KB Output is correct
3 Correct 610 ms 147396 KB Output is correct
4 Correct 631 ms 147184 KB Output is correct
5 Correct 530 ms 147816 KB Output is correct
6 Correct 537 ms 147624 KB Output is correct
7 Correct 102 ms 145756 KB Output is correct
8 Correct 104 ms 145080 KB Output is correct
9 Correct 906 ms 149328 KB Output is correct
10 Correct 927 ms 149156 KB Output is correct
11 Correct 903 ms 147532 KB Output is correct
12 Correct 966 ms 149300 KB Output is correct
13 Correct 284 ms 147400 KB Output is correct
14 Correct 391 ms 148536 KB Output is correct
15 Correct 177 ms 147408 KB Output is correct
16 Correct 198 ms 148196 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 151312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 143440 KB Output is correct
2 Correct 47 ms 143336 KB Output is correct
3 Correct 44 ms 143452 KB Output is correct
4 Correct 45 ms 143308 KB Output is correct
5 Correct 40 ms 143392 KB Output is correct
6 Correct 41 ms 143448 KB Output is correct
7 Correct 44 ms 143444 KB Output is correct
8 Correct 44 ms 143504 KB Output is correct
9 Correct 43 ms 143452 KB Output is correct
10 Correct 50 ms 143456 KB Output is correct
11 Correct 50 ms 143440 KB Output is correct
12 Correct 43 ms 143444 KB Output is correct
13 Correct 42 ms 143404 KB Output is correct
14 Correct 45 ms 143444 KB Output is correct
15 Correct 41 ms 143444 KB Output is correct
16 Correct 43 ms 143440 KB Output is correct
17 Correct 42 ms 143440 KB Output is correct
18 Correct 44 ms 143444 KB Output is correct
19 Correct 41 ms 143480 KB Output is correct
20 Correct 46 ms 143436 KB Output is correct
21 Correct 637 ms 147428 KB Output is correct
22 Correct 500 ms 147464 KB Output is correct
23 Correct 610 ms 147396 KB Output is correct
24 Correct 631 ms 147184 KB Output is correct
25 Correct 530 ms 147816 KB Output is correct
26 Correct 537 ms 147624 KB Output is correct
27 Correct 102 ms 145756 KB Output is correct
28 Correct 104 ms 145080 KB Output is correct
29 Correct 906 ms 149328 KB Output is correct
30 Correct 927 ms 149156 KB Output is correct
31 Correct 903 ms 147532 KB Output is correct
32 Correct 966 ms 149300 KB Output is correct
33 Correct 284 ms 147400 KB Output is correct
34 Correct 391 ms 148536 KB Output is correct
35 Correct 177 ms 147408 KB Output is correct
36 Correct 198 ms 148196 KB Output is correct
37 Correct 716 ms 147196 KB Output is correct
38 Correct 756 ms 147152 KB Output is correct
39 Correct 83 ms 144976 KB Output is correct
40 Correct 95 ms 145224 KB Output is correct
41 Execution timed out 1064 ms 147752 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 152648 KB Output is correct
2 Correct 472 ms 152656 KB Output is correct
3 Correct 577 ms 151644 KB Output is correct
4 Correct 521 ms 148028 KB Output is correct
5 Correct 615 ms 148760 KB Output is correct
6 Correct 692 ms 149288 KB Output is correct
7 Correct 92 ms 146856 KB Output is correct
8 Correct 92 ms 146876 KB Output is correct
9 Execution timed out 1049 ms 155736 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 143440 KB Output is correct
2 Correct 47 ms 143336 KB Output is correct
3 Correct 44 ms 143452 KB Output is correct
4 Correct 45 ms 143308 KB Output is correct
5 Correct 40 ms 143392 KB Output is correct
6 Correct 41 ms 143448 KB Output is correct
7 Correct 44 ms 143444 KB Output is correct
8 Correct 44 ms 143504 KB Output is correct
9 Correct 43 ms 143452 KB Output is correct
10 Correct 50 ms 143456 KB Output is correct
11 Correct 50 ms 143440 KB Output is correct
12 Correct 43 ms 143444 KB Output is correct
13 Correct 42 ms 143404 KB Output is correct
14 Correct 45 ms 143444 KB Output is correct
15 Correct 41 ms 143444 KB Output is correct
16 Correct 43 ms 143440 KB Output is correct
17 Correct 42 ms 143440 KB Output is correct
18 Correct 44 ms 143444 KB Output is correct
19 Correct 41 ms 143480 KB Output is correct
20 Correct 46 ms 143436 KB Output is correct
21 Correct 43 ms 143444 KB Output is correct
22 Correct 43 ms 143448 KB Output is correct
23 Correct 44 ms 143408 KB Output is correct
24 Correct 42 ms 143444 KB Output is correct
25 Correct 47 ms 143188 KB Output is correct
26 Correct 40 ms 143184 KB Output is correct
27 Correct 43 ms 143440 KB Output is correct
28 Correct 43 ms 143336 KB Output is correct
29 Correct 45 ms 143460 KB Output is correct
30 Correct 43 ms 143308 KB Output is correct
31 Correct 44 ms 143452 KB Output is correct
32 Correct 45 ms 143484 KB Output is correct
33 Correct 42 ms 143444 KB Output is correct
34 Correct 43 ms 143444 KB Output is correct
35 Correct 44 ms 143380 KB Output is correct
36 Correct 44 ms 143444 KB Output is correct
37 Correct 40 ms 143444 KB Output is correct
38 Correct 44 ms 143368 KB Output is correct
39 Correct 637 ms 147428 KB Output is correct
40 Correct 500 ms 147464 KB Output is correct
41 Correct 610 ms 147396 KB Output is correct
42 Correct 631 ms 147184 KB Output is correct
43 Correct 530 ms 147816 KB Output is correct
44 Correct 537 ms 147624 KB Output is correct
45 Correct 102 ms 145756 KB Output is correct
46 Correct 104 ms 145080 KB Output is correct
47 Correct 906 ms 149328 KB Output is correct
48 Correct 927 ms 149156 KB Output is correct
49 Correct 903 ms 147532 KB Output is correct
50 Correct 966 ms 149300 KB Output is correct
51 Correct 284 ms 147400 KB Output is correct
52 Correct 391 ms 148536 KB Output is correct
53 Correct 177 ms 147408 KB Output is correct
54 Correct 198 ms 148196 KB Output is correct
55 Correct 716 ms 147196 KB Output is correct
56 Correct 756 ms 147152 KB Output is correct
57 Correct 83 ms 144976 KB Output is correct
58 Correct 95 ms 145224 KB Output is correct
59 Execution timed out 1064 ms 147752 KB Time limit exceeded
60 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 143440 KB Output is correct
2 Correct 47 ms 143336 KB Output is correct
3 Correct 44 ms 143452 KB Output is correct
4 Correct 45 ms 143308 KB Output is correct
5 Correct 40 ms 143392 KB Output is correct
6 Correct 41 ms 143448 KB Output is correct
7 Correct 44 ms 143444 KB Output is correct
8 Correct 44 ms 143504 KB Output is correct
9 Correct 43 ms 143452 KB Output is correct
10 Correct 50 ms 143456 KB Output is correct
11 Correct 50 ms 143440 KB Output is correct
12 Correct 43 ms 143444 KB Output is correct
13 Correct 42 ms 143404 KB Output is correct
14 Correct 45 ms 143444 KB Output is correct
15 Correct 41 ms 143444 KB Output is correct
16 Correct 43 ms 143440 KB Output is correct
17 Correct 42 ms 143440 KB Output is correct
18 Correct 44 ms 143444 KB Output is correct
19 Correct 41 ms 143480 KB Output is correct
20 Correct 46 ms 143436 KB Output is correct
21 Correct 43 ms 143444 KB Output is correct
22 Correct 43 ms 143448 KB Output is correct
23 Correct 44 ms 143408 KB Output is correct
24 Correct 42 ms 143444 KB Output is correct
25 Correct 47 ms 143188 KB Output is correct
26 Correct 40 ms 143184 KB Output is correct
27 Correct 43 ms 143440 KB Output is correct
28 Correct 43 ms 143336 KB Output is correct
29 Correct 45 ms 143460 KB Output is correct
30 Correct 43 ms 143308 KB Output is correct
31 Correct 44 ms 143452 KB Output is correct
32 Correct 45 ms 143484 KB Output is correct
33 Correct 42 ms 143444 KB Output is correct
34 Correct 43 ms 143444 KB Output is correct
35 Correct 44 ms 143380 KB Output is correct
36 Correct 44 ms 143444 KB Output is correct
37 Correct 40 ms 143444 KB Output is correct
38 Correct 44 ms 143368 KB Output is correct
39 Correct 637 ms 147428 KB Output is correct
40 Correct 500 ms 147464 KB Output is correct
41 Correct 610 ms 147396 KB Output is correct
42 Correct 631 ms 147184 KB Output is correct
43 Correct 530 ms 147816 KB Output is correct
44 Correct 537 ms 147624 KB Output is correct
45 Correct 102 ms 145756 KB Output is correct
46 Correct 104 ms 145080 KB Output is correct
47 Correct 906 ms 149328 KB Output is correct
48 Correct 927 ms 149156 KB Output is correct
49 Correct 903 ms 147532 KB Output is correct
50 Correct 966 ms 149300 KB Output is correct
51 Correct 284 ms 147400 KB Output is correct
52 Correct 391 ms 148536 KB Output is correct
53 Correct 177 ms 147408 KB Output is correct
54 Correct 198 ms 148196 KB Output is correct
55 Execution timed out 1016 ms 151312 KB Time limit exceeded
56 Halted 0 ms 0 KB -