oj.uz

Submission #521776

# Submission time Handle Problem Language Result Execution time Memory
521776 2022-02-03T03:58:09 Z amunduzbaev IOI Fever (JOI21_fever) C++14
100 / 100
 4956 ms 438716 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int N = 1e5 + 5;
const int MAX = 1e18;
struct node{
	int a, b, p, t;
};

bool operator < (node y, node x){
	if(y.a + y.b == x.a + x.b) return y.a < x.a;
	return y.a + y.b < x.a + x.b;
}

node Min(node& a, node& b){
	if(a.a < b.a) return a;
	return b;
}

const int M = (1 << 18);

struct ST{
	vector<node> tree, mn;
	vector<int> p[2];
	//~ int p[2][1 << 18];
	
	void init(){
		p[0].resize(M, MAX), p[1].resize(M, -1);
		tree.resize(M, {MAX, MAX, MAX, MAX}), mn.resize(M, {MAX, MAX, MAX, MAX});
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx || p[0][x] == MAX) return;
		if((node){mn[x<<1].a, p[0][x]} < tree[x<<1]){
			tree[x<<1] = {mn[x<<1].a, p[0][x], mn[x<<1].p, p[1][x]};
		} 
		if((node){mn[x<<1|1].a, p[0][x]} < tree[x<<1|1]){
			tree[x<<1|1] = {mn[x<<1|1].a, p[0][x], mn[x<<1|1].p, p[1][x]};
		} 
		if(p[0][x<<1] > p[0][x]) p[0][x<<1] = p[0][x], p[1][x<<1] = p[1][x];
		if(p[0][x<<1|1] > p[0][x]) p[0][x<<1|1] = p[0][x], p[1][x<<1|1] = p[1][x];
		p[0][x] = MAX;
		p[1][x] = -1;
	}
	
	void sett(int i, node v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = mn[x] = v; return; }
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		mn[x] = Min(mn[x<<1], mn[x<<1|1]);
	}
	
	void umin(int l, int r, int v, int t, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if((node){mn[x].a, v} < tree[x]) tree[x] = {mn[x].a, v, mn[x].p, t};
			if(p[0][x] > v){
				p[0][x] = v;
				p[1][x] = t;
			}
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		umin(l, r, v, t, lx, m, x<<1), umin(l, r, v, t, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		mn[x] = Min(mn[x<<1], mn[x<<1|1]);
	}
	
	//~ ar<int, 3> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		//~ if(lx > r || rx < l) return {MAX + MAX, MAX, MAX};
		//~ if(lx >= l && rx <= r) return {tree[x].a + tree[x].b, tree[x].p, tree[x].t};
		//~ int m = (lx + rx) >> 1;
		//~ push(x, lx, rx);
		//~ return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	//~ }
};

ar<int, 2> r[8][N];
int pos[8][N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 2>> p(n);
	for(int i=0;i<n;i++) cin>>p[i][0]>>p[i][1];
	map<int, vector<int>> mm[8];
	for(int i=0;i<n;i++){
		mm[0][p[i][0] - p[i][1]].push_back(i);
		mm[1][p[i][0] - p[i][1]].push_back(i);
		mm[2][p[i][0] + p[i][1]].push_back(i);
		mm[3][p[i][0] + p[i][1]].push_back(i);
		mm[4][p[i][1]].push_back(i);
		mm[5][p[i][1]].push_back(i);
		mm[6][p[i][0]].push_back(i);
		mm[7][p[i][0]].push_back(i);
	}
	
	for(int t=0;t<8;t++){
		int last = 0;
		for(auto& [x, v] : mm[t]){
			sort(v.begin(), v.end(), [&](int i, int j){
				if(t < 6) return p[i][0] < p[j][0];
				return p[i][1] < p[j][1];
			});
			
			for(int i=0;i<(int)v.size();i++){
				r[t][v[i]] = {last, last + (int)v.size() - 1};
				pos[t][v[i]] = last + i;
			} last += v.size();
		}
	}
	
	auto get = [&](int i, int j){
		if(j%2 == 0 && j < 4) return 2 * p[i][0];
		if(j%2 == 1 && j < 4) return -2 * p[i][0];
		if(j == 4) return p[i][0];
		if(j == 5) return -p[i][0];
		if(j == 6) return p[i][1];
		if(j == 7) return -p[i][1];
		assert(0);
	};
	
	vector<ST> tree(8);
	for(int j=0;j<8;j++){
		tree[j].init();
		for(int i=0;i<n;i++){
			tree[j].sett(pos[j][i], {get(i, j), MAX, i, -1});
		}
	}
	int ans = 0;
	auto is = [&](int a, int b, int t){
		return (abs(p[a][0] - p[b][0]) + abs(p[a][1] - p[b][1]) > t);
	};
	vector<ST> tmp = tree;
	
	for(int t=0;t<4;t++){
		tree = tmp;
		
		for(int j=0;j<8;j++){
			tree[j].sett(pos[j][0], {0, 0, 0, t});
		}
		
		auto find = [&]() -> ar<int, 3>{
			ar<int, 3> r; r[0] = MAX;
			for(int j=0;j<8;j++){
				auto tt = tree[j].tree[1];
				if(tt.a + tt.b < r[0]) r = {tt.a + tt.b, tt.p, tt.t};
			}
			
			if(~r[2] && ~r[1]){
				for(int j=0;j<8;j++){
					tree[j].sett(pos[j][r[1]], {MAX, -1, -1, -1});
				}
			}
			return r;
		};
		
		int res = 0;
		while(1){
			auto u = find();
			
			if(u[1] == -1 || u[2] == -1) break;
			res++;
			
			int i = u[1], t = u[2], tim = u[0];
			{
				auto& v = mm[0][p[i][0] - p[i][1]];
				if(t == 0 || t == 1){
					int lx = pos[0][i] - r[0][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[0][i][0], rx = r[0][i][1];
						tree[0].umin(lx, rx, -2 * p[i][0], (t == 0 ? 3 : 2));
					}
				} else {
					int lx = 0, rx = pos[1][i] - r[1][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m], tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[1][i][0], rx += r[1][i][0];
						tree[1].umin(lx, rx, 2 * p[i][0], (t == 2 ? 1 : 0));
					}
				}
			}
			
			{
				auto& v = mm[2][p[i][0] + p[i][1]];
				if(t == 1 || t == 2){
					int lx = pos[2][i] - r[2][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[2][i][0], rx = r[2][i][1];
						tree[2].umin(lx, rx, -2 * p[i][0], (t == 1 ? 0 : 3));
					}
				} else {
					int lx = 0, rx = pos[3][i] - r[3][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m], tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[3][i][0], rx += r[3][i][0];
						tree[3].umin(lx, rx, 2 * p[i][0], (t == 0 ? 1 : 2));
					}
				}
			}
			//~ cout<<"here"<<endl;
			{
				auto& v = mm[4][p[i][1]];
				if(t == 1){
					int lx = pos[4][i] - r[4][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[4][i][0], rx = r[4][i][1];
						tree[4].umin(lx, rx, -p[i][0], 3);
					}
				} if(t == 3){
					int lx = 0, rx = pos[5][i] - r[5][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m],  tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[5][i][0], rx += r[5][i][0];
						tree[5].umin(lx, rx, p[i][0], 1);
					}
				}
			}
			//~ cout<<"here"<<endl;
			{
				auto& v = mm[6][p[i][0]];
				if(t == 0){
					int lx = pos[6][i] - r[6][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[6][i][0], rx = r[6][i][1];
						tree[6].umin(lx, rx, -p[i][1], 2);
					}
				} if(t == 2){
					int lx = 0, rx = pos[7][i] - r[7][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m],  tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[7][i][0], rx += r[7][i][0];
						tree[7].umin(lx, rx, p[i][1], 0);
					}
				}
			}
			
			//~ cout<<"here"<<endl;
		}
		
		ans = max(ans, res);
	}
	
	cout<<ans<<"\n";
}

Compilation message

fever.cpp: In function 'int main()':
fever.cpp:107:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |   for(auto& [x, v] : mm[t]){
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 329172 KB Output is correct
2 Correct 210 ms 328988 KB Output is correct
3 Correct 210 ms 328900 KB Output is correct
4 Correct 212 ms 329072 KB Output is correct
5 Correct 210 ms 328992 KB Output is correct
6 Correct 219 ms 328984 KB Output is correct
7 Correct 214 ms 328900 KB Output is correct
8 Correct 212 ms 329104 KB Output is correct
9 Correct 209 ms 328900 KB Output is correct
10 Correct 210 ms 328920 KB Output is correct
11 Correct 217 ms 328904 KB Output is correct
12 Correct 216 ms 328900 KB Output is correct
13 Correct 212 ms 329000 KB Output is correct
14 Correct 227 ms 328988 KB Output is correct
15 Correct 221 ms 328916 KB Output is correct
16 Correct 211 ms 328868 KB Output is correct
17 Correct 215 ms 328944 KB Output is correct
18 Correct 211 ms 328996 KB Output is correct
19 Correct 211 ms 328868 KB Output is correct
20 Correct 223 ms 328900 KB Output is correct
21 Correct 210 ms 328900 KB Output is correct
22 Correct 213 ms 328868 KB Output is correct
23 Correct 219 ms 329112 KB Output is correct
24 Correct 211 ms 328892 KB Output is correct
25 Correct 213 ms 328940 KB Output is correct
26 Correct 213 ms 328884 KB Output is correct
27 Correct 214 ms 328900 KB Output is correct
28 Correct 210 ms 328872 KB Output is correct
29 Correct 211 ms 328872 KB Output is correct
30 Correct 218 ms 329052 KB Output is correct
31 Correct 215 ms 328988 KB Output is correct
32 Correct 210 ms 328952 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 329172 KB Output is correct
2 Correct 210 ms 328988 KB Output is correct
3 Correct 210 ms 328900 KB Output is correct
4 Correct 212 ms 329072 KB Output is correct
5 Correct 210 ms 328992 KB Output is correct
6 Correct 219 ms 328984 KB Output is correct
7 Correct 214 ms 328900 KB Output is correct
8 Correct 212 ms 329104 KB Output is correct
9 Correct 209 ms 328900 KB Output is correct
10 Correct 210 ms 328920 KB Output is correct
11 Correct 217 ms 328904 KB Output is correct
12 Correct 216 ms 328900 KB Output is correct
13 Correct 212 ms 329000 KB Output is correct
14 Correct 227 ms 328988 KB Output is correct
15 Correct 221 ms 328916 KB Output is correct
16 Correct 211 ms 328868 KB Output is correct
17 Correct 215 ms 328944 KB Output is correct
18 Correct 211 ms 328996 KB Output is correct
19 Correct 211 ms 328868 KB Output is correct
20 Correct 223 ms 328900 KB Output is correct
21 Correct 210 ms 328900 KB Output is correct
22 Correct 213 ms 328868 KB Output is correct
23 Correct 219 ms 329112 KB Output is correct
24 Correct 211 ms 328892 KB Output is correct
25 Correct 213 ms 328940 KB Output is correct
26 Correct 213 ms 328884 KB Output is correct
27 Correct 214 ms 328900 KB Output is correct
28 Correct 210 ms 328872 KB Output is correct
29 Correct 211 ms 328872 KB Output is correct
30 Correct 218 ms 329052 KB Output is correct
31 Correct 215 ms 328988 KB Output is correct
32 Correct 210 ms 328952 KB Output is correct
33 Correct 218 ms 329052 KB Output is correct
34 Correct 218 ms 328976 KB Output is correct
35 Correct 215 ms 329000 KB Output is correct
36 Correct 216 ms 329108 KB Output is correct
37 Correct 212 ms 328896 KB Output is correct
38 Correct 214 ms 328884 KB Output is correct
39 Correct 215 ms 328992 KB Output is correct
40 Correct 218 ms 328948 KB Output is correct
41 Correct 220 ms 328992 KB Output is correct
42 Correct 212 ms 328972 KB Output is correct
43 Correct 218 ms 328968 KB Output is correct
44 Correct 210 ms 328896 KB Output is correct
45 Correct 216 ms 328928 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 329196 KB Output is correct
2 Correct 213 ms 329072 KB Output is correct
3 Correct 212 ms 329072 KB Output is correct
4 Correct 217 ms 329020 KB Output is correct
5 Correct 213 ms 329028 KB Output is correct
6 Correct 213 ms 328972 KB Output is correct
7 Correct 221 ms 329160 KB Output is correct
8 Correct 216 ms 329028 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 329172 KB Output is correct
2 Correct 210 ms 328988 KB Output is correct
3 Correct 210 ms 328900 KB Output is correct
4 Correct 212 ms 329072 KB Output is correct
5 Correct 210 ms 328992 KB Output is correct
6 Correct 219 ms 328984 KB Output is correct
7 Correct 214 ms 328900 KB Output is correct
8 Correct 212 ms 329104 KB Output is correct
9 Correct 209 ms 328900 KB Output is correct
10 Correct 210 ms 328920 KB Output is correct
11 Correct 217 ms 328904 KB Output is correct
12 Correct 216 ms 328900 KB Output is correct
13 Correct 212 ms 329000 KB Output is correct
14 Correct 227 ms 328988 KB Output is correct
15 Correct 221 ms 328916 KB Output is correct
16 Correct 211 ms 328868 KB Output is correct
17 Correct 215 ms 328944 KB Output is correct
18 Correct 211 ms 328996 KB Output is correct
19 Correct 211 ms 328868 KB Output is correct
20 Correct 223 ms 328900 KB Output is correct
21 Correct 210 ms 328900 KB Output is correct
22 Correct 213 ms 328868 KB Output is correct
23 Correct 219 ms 329112 KB Output is correct
24 Correct 211 ms 328892 KB Output is correct
25 Correct 213 ms 328940 KB Output is correct
26 Correct 213 ms 328884 KB Output is correct
27 Correct 214 ms 328900 KB Output is correct
28 Correct 210 ms 328872 KB Output is correct
29 Correct 211 ms 328872 KB Output is correct
30 Correct 218 ms 329052 KB Output is correct
31 Correct 215 ms 328988 KB Output is correct
32 Correct 210 ms 328952 KB Output is correct
33 Correct 218 ms 329052 KB Output is correct
34 Correct 218 ms 328976 KB Output is correct
35 Correct 215 ms 329000 KB Output is correct
36 Correct 216 ms 329108 KB Output is correct
37 Correct 212 ms 328896 KB Output is correct
38 Correct 214 ms 328884 KB Output is correct
39 Correct 215 ms 328992 KB Output is correct
40 Correct 218 ms 328948 KB Output is correct
41 Correct 220 ms 328992 KB Output is correct
42 Correct 212 ms 328972 KB Output is correct
43 Correct 218 ms 328968 KB Output is correct
44 Correct 210 ms 328896 KB Output is correct
45 Correct 216 ms 328928 KB Output is correct
46 Correct 225 ms 329196 KB Output is correct
47 Correct 213 ms 329072 KB Output is correct
48 Correct 212 ms 329072 KB Output is correct
49 Correct 217 ms 329020 KB Output is correct
50 Correct 213 ms 329028 KB Output is correct
51 Correct 213 ms 328972 KB Output is correct
52 Correct 221 ms 329160 KB Output is correct
53 Correct 216 ms 329028 KB Output is correct
54 Correct 221 ms 329028 KB Output is correct
55 Correct 228 ms 329012 KB Output is correct
56 Correct 224 ms 329076 KB Output is correct
57 Correct 219 ms 329028 KB Output is correct
58 Correct 226 ms 329152 KB Output is correct
59 Correct 211 ms 329072 KB Output is correct
60 Correct 216 ms 328996 KB Output is correct
61 Correct 220 ms 329200 KB Output is correct
62 Correct 213 ms 329008 KB Output is correct
63 Correct 213 ms 329080 KB Output is correct
64 Correct 219 ms 329196 KB Output is correct
65 Correct 222 ms 328976 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 329172 KB Output is correct
2 Correct 210 ms 328988 KB Output is correct
3 Correct 210 ms 328900 KB Output is correct
4 Correct 212 ms 329072 KB Output is correct
5 Correct 210 ms 328992 KB Output is correct
6 Correct 219 ms 328984 KB Output is correct
7 Correct 214 ms 328900 KB Output is correct
8 Correct 212 ms 329104 KB Output is correct
9 Correct 209 ms 328900 KB Output is correct
10 Correct 210 ms 328920 KB Output is correct
11 Correct 217 ms 328904 KB Output is correct
12 Correct 216 ms 328900 KB Output is correct
13 Correct 212 ms 329000 KB Output is correct
14 Correct 227 ms 328988 KB Output is correct
15 Correct 221 ms 328916 KB Output is correct
16 Correct 211 ms 328868 KB Output is correct
17 Correct 215 ms 328944 KB Output is correct
18 Correct 211 ms 328996 KB Output is correct
19 Correct 211 ms 328868 KB Output is correct
20 Correct 223 ms 328900 KB Output is correct
21 Correct 210 ms 328900 KB Output is correct
22 Correct 213 ms 328868 KB Output is correct
23 Correct 219 ms 329112 KB Output is correct
24 Correct 211 ms 328892 KB Output is correct
25 Correct 213 ms 328940 KB Output is correct
26 Correct 213 ms 328884 KB Output is correct
27 Correct 214 ms 328900 KB Output is correct
28 Correct 210 ms 328872 KB Output is correct
29 Correct 211 ms 328872 KB Output is correct
30 Correct 218 ms 329052 KB Output is correct
31 Correct 215 ms 328988 KB Output is correct
32 Correct 210 ms 328952 KB Output is correct
33 Correct 218 ms 329052 KB Output is correct
34 Correct 218 ms 328976 KB Output is correct
35 Correct 215 ms 329000 KB Output is correct
36 Correct 216 ms 329108 KB Output is correct
37 Correct 212 ms 328896 KB Output is correct
38 Correct 214 ms 328884 KB Output is correct
39 Correct 215 ms 328992 KB Output is correct
40 Correct 218 ms 328948 KB Output is correct
41 Correct 220 ms 328992 KB Output is correct
42 Correct 212 ms 328972 KB Output is correct
43 Correct 218 ms 328968 KB Output is correct
44 Correct 210 ms 328896 KB Output is correct
45 Correct 216 ms 328928 KB Output is correct
46 Correct 225 ms 329196 KB Output is correct
47 Correct 213 ms 329072 KB Output is correct
48 Correct 212 ms 329072 KB Output is correct
49 Correct 217 ms 329020 KB Output is correct
50 Correct 213 ms 329028 KB Output is correct
51 Correct 213 ms 328972 KB Output is correct
52 Correct 221 ms 329160 KB Output is correct
53 Correct 216 ms 329028 KB Output is correct
54 Correct 221 ms 329028 KB Output is correct
55 Correct 228 ms 329012 KB Output is correct
56 Correct 224 ms 329076 KB Output is correct
57 Correct 219 ms 329028 KB Output is correct
58 Correct 226 ms 329152 KB Output is correct
59 Correct 211 ms 329072 KB Output is correct
60 Correct 216 ms 328996 KB Output is correct
61 Correct 220 ms 329200 KB Output is correct
62 Correct 213 ms 329008 KB Output is correct
63 Correct 213 ms 329080 KB Output is correct
64 Correct 219 ms 329196 KB Output is correct
65 Correct 222 ms 328976 KB Output is correct
66 Correct 227 ms 331832 KB Output is correct
67 Correct 231 ms 331888 KB Output is correct
68 Correct 228 ms 332132 KB Output is correct
69 Correct 281 ms 330000 KB Output is correct
70 Correct 253 ms 330236 KB Output is correct
71 Correct 244 ms 330396 KB Output is correct
72 Correct 229 ms 331332 KB Output is correct
73 Correct 236 ms 332272 KB Output is correct
74 Correct 242 ms 331588 KB Output is correct
75 Correct 272 ms 331536 KB Output is correct
76 Correct 237 ms 331912 KB Output is correct
77 Correct 233 ms 331684 KB Output is correct
78 Correct 245 ms 331928 KB Output is correct
79 Correct 241 ms 331844 KB Output is correct
80 Correct 231 ms 332084 KB Output is correct
81 Correct 241 ms 331840 KB Output is correct
82 Correct 258 ms 331760 KB Output is correct
83 Correct 250 ms 331628 KB Output is correct
84 Correct 227 ms 330644 KB Output is correct
85 Correct 227 ms 329980 KB Output is correct
86 Correct 228 ms 329980 KB Output is correct
87 Correct 226 ms 330388 KB Output is correct
88 Correct 250 ms 331640 KB Output is correct
89 Correct 247 ms 331568 KB Output is correct
90 Correct 239 ms 331484 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 329172 KB Output is correct
2 Correct 210 ms 328988 KB Output is correct
3 Correct 210 ms 328900 KB Output is correct
4 Correct 212 ms 329072 KB Output is correct
5 Correct 210 ms 328992 KB Output is correct
6 Correct 219 ms 328984 KB Output is correct
7 Correct 214 ms 328900 KB Output is correct
8 Correct 212 ms 329104 KB Output is correct
9 Correct 209 ms 328900 KB Output is correct
10 Correct 210 ms 328920 KB Output is correct
11 Correct 217 ms 328904 KB Output is correct
12 Correct 216 ms 328900 KB Output is correct
13 Correct 212 ms 329000 KB Output is correct
14 Correct 227 ms 328988 KB Output is correct
15 Correct 221 ms 328916 KB Output is correct
16 Correct 211 ms 328868 KB Output is correct
17 Correct 215 ms 328944 KB Output is correct
18 Correct 211 ms 328996 KB Output is correct
19 Correct 211 ms 328868 KB Output is correct
20 Correct 223 ms 328900 KB Output is correct
21 Correct 210 ms 328900 KB Output is correct
22 Correct 213 ms 328868 KB Output is correct
23 Correct 219 ms 329112 KB Output is correct
24 Correct 211 ms 328892 KB Output is correct
25 Correct 213 ms 328940 KB Output is correct
26 Correct 213 ms 328884 KB Output is correct
27 Correct 214 ms 328900 KB Output is correct
28 Correct 210 ms 328872 KB Output is correct
29 Correct 211 ms 328872 KB Output is correct
30 Correct 218 ms 329052 KB Output is correct
31 Correct 215 ms 328988 KB Output is correct
32 Correct 210 ms 328952 KB Output is correct
33 Correct 218 ms 329052 KB Output is correct
34 Correct 218 ms 328976 KB Output is correct
35 Correct 215 ms 329000 KB Output is correct
36 Correct 216 ms 329108 KB Output is correct
37 Correct 212 ms 328896 KB Output is correct
38 Correct 214 ms 328884 KB Output is correct
39 Correct 215 ms 328992 KB Output is correct
40 Correct 218 ms 328948 KB Output is correct
41 Correct 220 ms 328992 KB Output is correct
42 Correct 212 ms 328972 KB Output is correct
43 Correct 218 ms 328968 KB Output is correct
44 Correct 210 ms 328896 KB Output is correct
45 Correct 216 ms 328928 KB Output is correct
46 Correct 225 ms 329196 KB Output is correct
47 Correct 213 ms 329072 KB Output is correct
48 Correct 212 ms 329072 KB Output is correct
49 Correct 217 ms 329020 KB Output is correct
50 Correct 213 ms 329028 KB Output is correct
51 Correct 213 ms 328972 KB Output is correct
52 Correct 221 ms 329160 KB Output is correct
53 Correct 216 ms 329028 KB Output is correct
54 Correct 221 ms 329028 KB Output is correct
55 Correct 228 ms 329012 KB Output is correct
56 Correct 224 ms 329076 KB Output is correct
57 Correct 219 ms 329028 KB Output is correct
58 Correct 226 ms 329152 KB Output is correct
59 Correct 211 ms 329072 KB Output is correct
60 Correct 216 ms 328996 KB Output is correct
61 Correct 220 ms 329200 KB Output is correct
62 Correct 213 ms 329008 KB Output is correct
63 Correct 213 ms 329080 KB Output is correct
64 Correct 219 ms 329196 KB Output is correct
65 Correct 222 ms 328976 KB Output is correct
66 Correct 1041 ms 406384 KB Output is correct
67 Correct 1250 ms 425588 KB Output is correct
68 Correct 1283 ms 436800 KB Output is correct
69 Correct 1677 ms 416700 KB Output is correct
70 Correct 2721 ms 416584 KB Output is correct
71 Correct 1291 ms 437064 KB Output is correct
72 Correct 1321 ms 436216 KB Output is correct
73 Correct 1515 ms 416964 KB Output is correct
74 Correct 1288 ms 436952 KB Output is correct
75 Correct 1445 ms 435476 KB Output is correct
76 Correct 1720 ms 417052 KB Output is correct
77 Correct 1281 ms 436940 KB Output is correct
78 Correct 1751 ms 415016 KB Output is correct
79 Correct 1712 ms 414996 KB Output is correct

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 329172 KB Output is correct
2 Correct 210 ms 328988 KB Output is correct
3 Correct 210 ms 328900 KB Output is correct
4 Correct 212 ms 329072 KB Output is correct
5 Correct 210 ms 328992 KB Output is correct
6 Correct 219 ms 328984 KB Output is correct
7 Correct 214 ms 328900 KB Output is correct
8 Correct 212 ms 329104 KB Output is correct
9 Correct 209 ms 328900 KB Output is correct
10 Correct 210 ms 328920 KB Output is correct
11 Correct 217 ms 328904 KB Output is correct
12 Correct 216 ms 328900 KB Output is correct
13 Correct 212 ms 329000 KB Output is correct
14 Correct 227 ms 328988 KB Output is correct
15 Correct 221 ms 328916 KB Output is correct
16 Correct 211 ms 328868 KB Output is correct
17 Correct 215 ms 328944 KB Output is correct
18 Correct 211 ms 328996 KB Output is correct
19 Correct 211 ms 328868 KB Output is correct
20 Correct 223 ms 328900 KB Output is correct
21 Correct 210 ms 328900 KB Output is correct
22 Correct 213 ms 328868 KB Output is correct
23 Correct 219 ms 329112 KB Output is correct
24 Correct 211 ms 328892 KB Output is correct
25 Correct 213 ms 328940 KB Output is correct
26 Correct 213 ms 328884 KB Output is correct
27 Correct 214 ms 328900 KB Output is correct
28 Correct 210 ms 328872 KB Output is correct
29 Correct 211 ms 328872 KB Output is correct
30 Correct 218 ms 329052 KB Output is correct
31 Correct 215 ms 328988 KB Output is correct
32 Correct 210 ms 328952 KB Output is correct
33 Correct 218 ms 329052 KB Output is correct
34 Correct 218 ms 328976 KB Output is correct
35 Correct 215 ms 329000 KB Output is correct
36 Correct 216 ms 329108 KB Output is correct
37 Correct 212 ms 328896 KB Output is correct
38 Correct 214 ms 328884 KB Output is correct
39 Correct 215 ms 328992 KB Output is correct
40 Correct 218 ms 328948 KB Output is correct
41 Correct 220 ms 328992 KB Output is correct
42 Correct 212 ms 328972 KB Output is correct
43 Correct 218 ms 328968 KB Output is correct
44 Correct 210 ms 328896 KB Output is correct
45 Correct 216 ms 328928 KB Output is correct
46 Correct 225 ms 329196 KB Output is correct
47 Correct 213 ms 329072 KB Output is correct
48 Correct 212 ms 329072 KB Output is correct
49 Correct 217 ms 329020 KB Output is correct
50 Correct 213 ms 329028 KB Output is correct
51 Correct 213 ms 328972 KB Output is correct
52 Correct 221 ms 329160 KB Output is correct
53 Correct 216 ms 329028 KB Output is correct
54 Correct 221 ms 329028 KB Output is correct
55 Correct 228 ms 329012 KB Output is correct
56 Correct 224 ms 329076 KB Output is correct
57 Correct 219 ms 329028 KB Output is correct
58 Correct 226 ms 329152 KB Output is correct
59 Correct 211 ms 329072 KB Output is correct
60 Correct 216 ms 328996 KB Output is correct
61 Correct 220 ms 329200 KB Output is correct
62 Correct 213 ms 329008 KB Output is correct
63 Correct 213 ms 329080 KB Output is correct
64 Correct 219 ms 329196 KB Output is correct
65 Correct 222 ms 328976 KB Output is correct
66 Correct 227 ms 331832 KB Output is correct
67 Correct 231 ms 331888 KB Output is correct
68 Correct 228 ms 332132 KB Output is correct
69 Correct 281 ms 330000 KB Output is correct
70 Correct 253 ms 330236 KB Output is correct
71 Correct 244 ms 330396 KB Output is correct
72 Correct 229 ms 331332 KB Output is correct
73 Correct 236 ms 332272 KB Output is correct
74 Correct 242 ms 331588 KB Output is correct
75 Correct 272 ms 331536 KB Output is correct
76 Correct 237 ms 331912 KB Output is correct
77 Correct 233 ms 331684 KB Output is correct
78 Correct 245 ms 331928 KB Output is correct
79 Correct 241 ms 331844 KB Output is correct
80 Correct 231 ms 332084 KB Output is correct
81 Correct 241 ms 331840 KB Output is correct
82 Correct 258 ms 331760 KB Output is correct
83 Correct 250 ms 331628 KB Output is correct
84 Correct 227 ms 330644 KB Output is correct
85 Correct 227 ms 329980 KB Output is correct
86 Correct 228 ms 329980 KB Output is correct
87 Correct 226 ms 330388 KB Output is correct
88 Correct 250 ms 331640 KB Output is correct
89 Correct 247 ms 331568 KB Output is correct
90 Correct 239 ms 331484 KB Output is correct
91 Correct 1041 ms 406384 KB Output is correct
92 Correct 1250 ms 425588 KB Output is correct
93 Correct 1283 ms 436800 KB Output is correct
94 Correct 1677 ms 416700 KB Output is correct
95 Correct 2721 ms 416584 KB Output is correct
96 Correct 1291 ms 437064 KB Output is correct
97 Correct 1321 ms 436216 KB Output is correct
98 Correct 1515 ms 416964 KB Output is correct
99 Correct 1288 ms 436952 KB Output is correct
100 Correct 1445 ms 435476 KB Output is correct
101 Correct 1720 ms 417052 KB Output is correct
102 Correct 1281 ms 436940 KB Output is correct
103 Correct 1751 ms 415016 KB Output is correct
104 Correct 1712 ms 414996 KB Output is correct
105 Correct 2976 ms 355056 KB Output is correct
106 Correct 3660 ms 359272 KB Output is correct
107 Correct 4956 ms 361492 KB Output is correct
108 Correct 3987 ms 362260 KB Output is correct
109 Correct 985 ms 370968 KB Output is correct
110 Correct 1222 ms 411088 KB Output is correct
111 Correct 1288 ms 438716 KB Output is correct
112 Correct 1271 ms 431424 KB Output is correct
113 Correct 1320 ms 431028 KB Output is correct
114 Correct 3560 ms 384860 KB Output is correct
115 Correct 1540 ms 418892 KB Output is correct
116 Correct 1271 ms 431368 KB Output is correct
117 Correct 1530 ms 429932 KB Output is correct
118 Correct 2668 ms 407108 KB Output is correct
119 Correct 2174 ms 418880 KB Output is correct
120 Correct 1273 ms 431312 KB Output is correct
121 Correct 1368 ms 433608 KB Output is correct
122 Correct 1610 ms 431532 KB Output is correct
123 Correct 1859 ms 418156 KB Output is correct
124 Correct 1847 ms 418424 KB Output is correct
125 Correct 785 ms 385096 KB Output is correct
126 Correct 588 ms 364140 KB Output is correct
127 Correct 767 ms 361436 KB Output is correct
128 Correct 586 ms 363728 KB Output is correct
129 Correct 683 ms 375568 KB Output is correct