Submission #701232

# Submission time Handle Problem Language Result Execution time Memory
701232 2023-02-20T15:14:01 Z minhcool Road Construction (JOI21_road_construction) C++17
65 / 100
10000 ms 721376 KB
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 250005 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, k;
 
ii a[N], b[N];
 
int savee[N];
 
map<ii, int> mp;
// type1[id]: (-x - y), type2[id]: (-x + y)
 
vector<int> x, y;
vector<int> type1[524290], type2[524290];
vector<int> bit1[524290], bit2[524290];
int mini1[524290], mini2[524290];
 
 
void build(int id, int l, int r){
	bit1[id].resize(r - l + 2), bit2[id].resize(r - l + 2);
	if(l == r){
		type1[id].pb(-b[l].fi - b[l].se);
		type2[id].pb(-b[l].fi + b[l].se);
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	for(auto it : type1[id << 1]) type1[id].pb(it);
	for(auto it : type2[id << 1]) type2[id].pb(it);
	for(auto it : type1[id << 1 | 1]) type1[id].pb(it);
	for(auto it : type2[id << 1 | 1]) type2[id].pb(it);
	sort(type1[id].begin(), type1[id].end());
	sort(type2[id].begin(), type2[id].end());
	type1[id].resize(unique(type1[id].begin(), type1[id].end()) - type1[id].begin());
	type2[id].resize(unique(type2[id].begin(), type2[id].end()) - type2[id].begin());
	bit1[id].resize(type1[id].size() + 1);
	bit2[id].resize(type2[id].size() + 1);
}
 
void upd1(int id, int id2){
	for(; id2 < bit1[id].size(); id2 += id2 & -id2) bit1[id][id2]++;
}
 
int get1(int id, int id2){
	int ans = 0;
	for(; id2; id2 -= id2 & -id2){
		ans += bit1[id][id2];
	}
	return ans;
}
 
void upd2(int id, int id2){
	for(; id2 < bit2[id].size(); id2 += id2 & -id2) bit2[id][id2]++;
}
 
int get2(int id, int id2){
	int ans = 0;
	for(; id2; id2 -= id2 & -id2){
		ans += bit2[id][id2];
	}
	return ans;
}
 
int cnt;
ii point;
 
vector<ii> u1[N], u2[N];
 
void prep(int id, int l, int r, int pos){
	int posi = lower_bound(type1[id].begin(), type1[id].end(), -point.fi - point.se) - type1[id].begin();
	u1[cnt].pb({id, posi});
	posi = lower_bound(type2[id].begin(), type2[id].end(), -point.fi + point.se) - type2[id].begin();
	u2[cnt].pb({id, posi});
	//upd1(id, posi);
	//upd2(id, posi);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) prep(id << 1, l, mid, pos);
	else prep(id << 1 | 1, mid + 1, r, pos);
}
 
/*
void upd(int id, int l, int r, int pos){
	//int posi = lower_bound(type1[id].begin(), type1[id].end(), -point.fi - point.se) - type1[id].begin();
	//int posi = 1;
	upd1(id, posi);
	//posi = lower_bound(type2[id].begin(), type2[id].end(), -point.fi + point.se) - type2[id].begin();
	upd2(id, posi);
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(pos <= mid) upd(id << 1, l, mid, pos);
	else upd(id << 1 | 1, mid + 1, r, pos);
}*/
 
int type, val;
 
vector<int> g1[N], g2[N];
vector<int> min_val1[524290], min_val2[524290];
int itr1[524290], itr2[524290];
 
void prep2(int id, int l, int r, int L, int R){// <= val, return no of pairs
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		if(!type){
			g1[cnt].pb(id);
			min_val1[id].pb(a[cnt].fi + a[cnt].se);
		}
		else{
			g2[cnt].pb(id);
			min_val2[id].pb(a[cnt].fi - a[cnt].se);
		}
		return;
	}
	int mid = (l + r) >> 1;
	prep2(id << 1, l, mid, L, R);
	prep2(id << 1 | 1, mid + 1, r, L, R);
}
 
bool cmp(ii a, ii b){
	return a.se < b.se;
}
 
priority_queue<int, vector<int>, greater<int>> pq;
 
int find_mn1(int id, int value){
	int answer = 0;
	for(int i = 19; i >= 0; i--){
		if((answer + (1LL << i)) >= bit1[id].size()) continue;
		if(value > bit1[id][answer + (1LL << i)]){
			value -= bit1[id][answer + (1LL << i)];
			answer += (1LL << i);
		}
	}
	return answer + 1;
}
 
int find_mn2(int id, int value){
	int answer = 0;
	for(int i = 19; i >= 0; i--){
		if((answer + (1LL << i)) >= bit2[id].size()) continue;
		if(value > bit2[id][answer + (1LL << i)]){
			value -= bit2[id][answer + (1LL << i)];
			answer += (1LL << i);
		}
	}
	return answer + 1;
}
 
int pluss;
 
void gett(int id, int l, int r, int L, int R){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		if(!type){
			int pos = upper_bound(type1[id].begin(), type1[id].end(), val) - type1[id].begin();
			pos--;
			int tempo = get1(id, pos);
			//cout << tempo << "\n";
			//return;
			for(int i = 1; i <= tempo; i++){
				int posi = find_mn1(id, i);
				//continue;
			//	cout << "OKAY " << type1[id][posi] << " " << plus << "\n";
				pq.push(type1[id][posi] + pluss);
			}
			return;
			//return get1(id, pos);
		}
		else{
			int pos = upper_bound(type2[id].begin(), type2[id].end(), val) - type2[id].begin();
			pos--;
			int tempo = get2(id, pos);
			//return;
			for(int i = 1; i <= tempo; i++){
				int posi = find_mn2(id, i);
				assert(posi < type2[id].size());
			//	cout << "OKAY " << type1[id][posi] << " " << plus << "\n";
				pq.push(type2[id][posi] + pluss);
			}
			return;
			//return get2(id, pos);
		}
	}
	int mid = (l + r) >> 1;
	gett(id << 1, l, mid, L, R);
	gett(id << 1 | 1, mid + 1, r, L, R);
}
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
void process(){
	cin >> n >> k;
	/*
	n = k = 130000;
	set<ii> se;
	while(se.size() < n) se.insert({rnd(-1e9, 1e9), rnd(-1e9, 1e9)});
	int cntt = 0;
	for(auto it : se){
	    cntt++;
	    a[cntt] = it;
	}*/
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi >> a[i].se;
		b[i] = a[i];
		x.pb(a[i].fi), y.pb(a[i].se);
	}
	sort(x.begin(), x.end()), sort(y.begin(), y.end());
	x.resize(unique(x.begin(), x.end()) - x.begin());
	y.resize(unique(y.begin(), y.end()) - y.begin());
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1, cmp);
	for(int i = 1; i <= n; i++) mp[b[i]] = i;
	build(1, 1, n);
	//return;
	for(int i = 1; i <= 524288; i++){
		type1[i].pb(-oo), type2[i].pb(-oo);
		sort(type1[i].begin(), type1[i].end());
		sort(type2[i].begin(), type2[i].end());
	}
	//return;
	int l = 1, r = 4e9 + 5;
	int itr = 0;
	for(int i = 1; i <= n; i++) savee[i] = mp[a[i]];
	for(int i = 1; i <= n; i++){
		cnt++;
		point = a[i];
		prep(1, 1, n, savee[i]);
		type = 0;
		prep2(1, 1, n, 1, savee[i]);
		type = 1;
		prep2(1, 1, n, savee[i] + 1, n);
	}
	for(int i = 1; i <= 524288; i++){
		//min_val1[i] = oo, min_val2[i] = oo;
		reverse(min_val1[i].begin(), min_val1[i].end());
		reverse(min_val2[i].begin(), min_val2[i].end());
		int mini = oo;
		for(int j = 0; j < min_val1[i].size(); j++){
		    mini = min(mini, min_val1[i][j]);
		    min_val1[i][j] = mini;
		}
		mini = oo;
		for(int j = 0; j < min_val2[i].size(); j++){
		    mini = min(mini, min_val2[i][j]);
		    min_val2[i][j] = mini;
		}
	}
	int tol_size = 0;
	for(int i = 1; i <= 524288; i++){
	    tol_size += min_val1[i].size();
	    tol_size += min_val2[i].size();
	}
	//cout << tol_size << "\n";
	int cnttt = 0, cnttt2 = 0;
		for(int i = 1; i <= 524288; i++){
			for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
			for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
			mini1[i] = mini2[i] = oo;
			itr1[i] = (int)min_val1[i].size() - 1;
			itr2[i] = (int)min_val2[i].size() - 1;
		}
  	//return;
	while(l < r){
		int mid = (l + r) >> 1;
			/*
			min_val3[i].resize(min_val1[i].size());
			for(int j = 0; j < min_val1[i].size(); j++) min_val3[i][j] = min_val1[i][j];
			min_val4[i].resize(min_val2[i].size());
			for(int j = 0; j < min_val2[i].size(); j++) min_val4[i][j] = min_val2[i][j];*/
			//min_val4[i] = min_val2[i];
		//}
		int answer = 0, total = 0;
		vector<ii> vc1, vc2;
		//unordered_set<int> vc3, vc4;
		for(int i = 1; i <= n; i++){
			int pos = savee[i];
		//	cout << pos << " ";
			val = mid - a[i].fi - a[i].se;
			//answer += get(1, 1, n, 1, pos);
			for(auto it : g1[i]){
			    //vc1.pb({it, 0});
			    itr1[it]--;
			    //min_val3[it].pop_back();
				if(mini1[it] == oo || type1[it][mini1[it]] > val) continue;
				cnttt2++;
				int pos = upper_bound(type1[it].begin(), type1[it].end(), val) - type1[it].begin();
				pos--;
				assert(mini1[it] == oo || pos >= mini1[it]);
				//cout << i << " " << it << " " << val << " " << pos << " " << mini1[it] << " " << get1(it, pos) << "\n";
				//assert(get1(it, pos) > 0);
				//cout << "OK " << id << " " << pos << " " << type1[id].size() << "\n";
				answer += get1(it, pos);
				if(answer >= k) break;
			}
			val = mid - a[i].fi + a[i].se;
			for(auto it : g2[i]){
			    //vc2.pb({it, 0});
			    itr2[it]--;
			    //min_val4[it].pop_back();
				if(mini2[it] == oo || type2[it][mini2[it]] > val) continue;
				cnttt2++;
				int pos = upper_bound(type2[it].begin(), type2[it].end(), val) - type2[it].begin();
				pos--;
				//assert(get2(it, pos) > 0);
				//cout << "OK " << id << " " << pos << " " << type2[id].size() << "\n";
				answer += get2(it, pos);
				if(answer >= k) break;
			}
			//answer += get(1, 1, n, pos + 1, n);
			//continue;
			//cout << answer << "\n";
			//point = a[i];
			if(answer >= k) break;
			for(auto it : u1[i]){
				if(itr1[it.fi] < 0 || (min_val1[it.fi][itr1[it.fi]] - a[i].fi - a[i].se) > mid) continue;
				total++;
				vc1.pb(it);
				upd1(it.fi, it.se);
				mini1[it.fi] = min(mini1[it.fi], it.se);
				cnttt++;
				if(total >= k) break;
			}
			for(auto it : u2[i]){
				if(itr2[it.fi] < 0 || (min_val2[it.fi][itr2[it.fi]] - a[i].fi + a[i].se) > mid) continue;
				total++;
				vc2.pb(it);
				upd2(it.fi, it.se);
				mini2[it.fi] = min(mini2[it.fi], it.se);
				cnttt++;
				if(total >= k) break;
			}
			if(total >= k){
			    answer = k;
			    break;
			}
			//upd(1, 1, n, pos);
		}
		for(auto it : vc1){
		    //assert(it.se > 0);
		    if(it.se) for(int j = it.se; j < bit1[it.fi].size(); j += j & -j) bit1[it.fi][j] = 0;
		    //for(int j = 0; j < bit1[i.].size(); j++) bit1[i][j] = 0;
		    mini1[it.fi] = oo;
		    itr1[it.fi] = (int)min_val1[it.fi].size() - 1;
		}
		for(auto it : vc2){
		    //assert(it.se > 0);
		    if(it.se) for(int j = it.se; j < bit2[it.fi].size(); j += j & -j) bit2[it.fi][j] = 0;
		    //for(int j = 0; j < bit1[i.].size(); j++) bit1[i][j] = 0;
		    mini2[it.fi] = oo;
		    itr2[it.fi] = (int)min_val2[it.fi].size() - 1;
		}
        for(int i = 1; i <= 524288; i++){
          itr1[i] = (int)min_val1[i].size() - 1;
          itr2[i] = (int)min_val2[i].size() - 1;
        }
		/*
		for(int i = 1; i <= 524288; i++){
			for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
			for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
			mini1[i] = mini2[i] = oo;
			itr1[i] = (int)min_val1[i].size() - 1;
			itr2[i] = (int)min_val2[i].size() - 1;
		}*/
			/*
			min_val3[i].resize(min_val1[i].size());
			for(int j = 0; j < min_val1[i].size(); j++) min_val3[i][j] = min_val1[i][j];
			min_val4[i].resize(min_val2[i].size());
			for(int j = 0; j < min_val2[i].size(); j++) min_val4[i][j] = min_val2[i][j];*/
			//min_val4[i] = min_val2[i];
		//}
		//cout << mid << " " << total << " " << answer << "\n";
		//return;
		//cout << mid << " " << answer << "\n";
		if(answer < k) l = mid + 1;
		else r = mid;
	//	itr++;
		//if(itr == 1) return;
	}
	//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
	//cout << cnttt << " " << cnttt2 << "\n";
	//return;
	//cout << l << "\n";
	l--;
	for(int i = 1; i <= 524288; i++){
		for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
		for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
	}
	for(int i = 1; i <= n; i++){
		int pos = mp[a[i]];
		type = 0, val = l - a[i].fi - a[i].se, pluss = a[i].fi + a[i].se;
		gett(1, 1, n, 1, pos);
		type = 1, val = l - a[i].fi + a[i].se, pluss = a[i].fi - a[i].se;
		gett(1, 1, n, pos + 1, n);
		for(auto it : u1[i]) upd1(it.fi, it.se);
		for(auto it : u2[i]) upd2(it.fi, it.se);
		//continue;
		//point = a[i];
		//upd(1, 1, n, pos);
	}
	l++;
	//return;
	//cout << pq.size() << '\n';
	//assert(pq.size() <= k);
	while(pq.size() < k) pq.push(l);
	for(int i = 1; i <= k; i++){
		int x = pq.top();
		pq.pop();
		cout << x << "\n";
	}
	//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("road.inp", "r", stdin);
	//freopen("road.out", "w", stdout);
	//cin.tie(0);
	process();
}

Compilation message

road_construction.cpp: In function 'void upd1(long long int, long long int)':
road_construction.cpp:55:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(; id2 < bit1[id].size(); id2 += id2 & -id2) bit1[id][id2]++;
      |        ~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void upd2(long long int, long long int)':
road_construction.cpp:67:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(; id2 < bit2[id].size(); id2 += id2 & -id2) bit2[id][id2]++;
      |        ~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'long long int find_mn1(long long int, long long int)':
road_construction.cpp:142:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   if((answer + (1LL << i)) >= bit1[id].size()) continue;
      |      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'long long int find_mn2(long long int, long long int)':
road_construction.cpp:154:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   if((answer + (1LL << i)) >= bit2[id].size()) continue;
      |      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from road_construction.cpp:1:
road_construction.cpp: In function 'void gett(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:190:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     assert(posi < type2[id].size());
      |            ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void process()':
road_construction.cpp:257:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  257 |   for(int j = 0; j < min_val1[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:262:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |   for(int j = 0; j < min_val2[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:275:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  275 |    for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
      |                   ~~^~~~~~~~~~~~~~~~
road_construction.cpp:276:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |    for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
      |                   ~~^~~~~~~~~~~~~~~~
road_construction.cpp:295:8: warning: unused variable 'pos' [-Wunused-variable]
  295 |    int pos = savee[i];
      |        ^~~
road_construction.cpp:359:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  359 |       if(it.se) for(int j = it.se; j < bit1[it.fi].size(); j += j & -j) bit1[it.fi][j] = 0;
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:366:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  366 |       if(it.se) for(int j = it.se; j < bit2[it.fi].size(); j += j & -j) bit2[it.fi][j] = 0;
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
road_construction.cpp:404:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  404 |   for(int j = 0; j < bit1[i].size(); j++) bit1[i][j] = 0;
      |                  ~~^~~~~~~~~~~~~~~~
road_construction.cpp:405:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  405 |   for(int j = 0; j < bit2[i].size(); j++) bit2[i][j] = 0;
      |                  ~~^~~~~~~~~~~~~~~~
road_construction.cpp:423:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  423 |  while(pq.size() < k) pq.push(l);
      |        ~~~~~~~~~~^~~
road_construction.cpp:241:6: warning: unused variable 'itr' [-Wunused-variable]
  241 |  int itr = 0;
      |      ^~~
# Verdict Execution time Memory Grader output
1 Correct 270 ms 152872 KB Output is correct
2 Correct 273 ms 152944 KB Output is correct
3 Correct 253 ms 152644 KB Output is correct
4 Correct 250 ms 152668 KB Output is correct
5 Correct 259 ms 151740 KB Output is correct
6 Correct 175 ms 148220 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9919 ms 716240 KB Output is correct
2 Correct 9737 ms 718656 KB Output is correct
3 Correct 249 ms 152468 KB Output is correct
4 Correct 8617 ms 717684 KB Output is correct
5 Correct 8866 ms 720040 KB Output is correct
6 Correct 8722 ms 719576 KB Output is correct
7 Correct 8089 ms 719352 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 8121 ms 709580 KB Output is correct
2 Correct 9242 ms 709692 KB Output is correct
3 Correct 162 ms 146904 KB Output is correct
4 Correct 6990 ms 709560 KB Output is correct
5 Correct 5980 ms 681980 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 8121 ms 709580 KB Output is correct
2 Correct 9242 ms 709692 KB Output is correct
3 Correct 162 ms 146904 KB Output is correct
4 Correct 6990 ms 709560 KB Output is correct
5 Correct 5980 ms 681980 KB Output is correct
6 Correct 9848 ms 709700 KB Output is correct
7 Correct 9464 ms 714668 KB Output is correct
8 Correct 160 ms 146824 KB Output is correct
9 Correct 163 ms 146944 KB Output is correct
10 Correct 9482 ms 714284 KB Output is correct
11 Correct 6922 ms 712524 KB Output is correct
12 Correct 7354 ms 687132 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 270 ms 152872 KB Output is correct
2 Correct 273 ms 152944 KB Output is correct
3 Correct 253 ms 152644 KB Output is correct
4 Correct 250 ms 152668 KB Output is correct
5 Correct 259 ms 151740 KB Output is correct
6 Correct 175 ms 148220 KB Output is correct
7 Correct 5960 ms 375800 KB Output is correct
8 Correct 5897 ms 375372 KB Output is correct
9 Correct 260 ms 152632 KB Output is correct
10 Correct 3850 ms 374048 KB Output is correct
11 Correct 3379 ms 372312 KB Output is correct
12 Correct 3522 ms 363244 KB Output is correct
13 Correct 3865 ms 364528 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 270 ms 152872 KB Output is correct
2 Correct 273 ms 152944 KB Output is correct
3 Correct 253 ms 152644 KB Output is correct
4 Correct 250 ms 152668 KB Output is correct
5 Correct 259 ms 151740 KB Output is correct
6 Correct 175 ms 148220 KB Output is correct
7 Correct 9919 ms 716240 KB Output is correct
8 Correct 9737 ms 718656 KB Output is correct
9 Correct 249 ms 152468 KB Output is correct
10 Correct 8617 ms 717684 KB Output is correct
11 Correct 8866 ms 720040 KB Output is correct
12 Correct 8722 ms 719576 KB Output is correct
13 Correct 8089 ms 719352 KB Output is correct
14 Correct 8121 ms 709580 KB Output is correct
15 Correct 9242 ms 709692 KB Output is correct
16 Correct 162 ms 146904 KB Output is correct
17 Correct 6990 ms 709560 KB Output is correct
18 Correct 5980 ms 681980 KB Output is correct
19 Correct 9848 ms 709700 KB Output is correct
20 Correct 9464 ms 714668 KB Output is correct
21 Correct 160 ms 146824 KB Output is correct
22 Correct 163 ms 146944 KB Output is correct
23 Correct 9482 ms 714284 KB Output is correct
24 Correct 6922 ms 712524 KB Output is correct
25 Correct 7354 ms 687132 KB Output is correct
26 Correct 5960 ms 375800 KB Output is correct
27 Correct 5897 ms 375372 KB Output is correct
28 Correct 260 ms 152632 KB Output is correct
29 Correct 3850 ms 374048 KB Output is correct
30 Correct 3379 ms 372312 KB Output is correct
31 Correct 3522 ms 363244 KB Output is correct
32 Correct 3865 ms 364528 KB Output is correct
33 Execution timed out 10095 ms 721376 KB Time limit exceeded
34 Halted 0 ms 0 KB -