Submission #1022054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022054		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	600 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 100;

int a[maxn];
int b[maxn];
int c[maxn];
int pref[maxn];
int suf[maxn];
int r[maxn];
int l[maxn];
vector<int> v;

int get(int i, int j){
	if(!i) return 0;
    ll x = max(0, (- i + a[i] + j + a[j]) / 2);
    return x * x;
}

ll f(int i){
	return get(v[l[i-1]], v[r[i]]) - get(v[l[i-1]], v[i-1]) - get(v[i], v[r[i]]) + get(v[i], v[i-1]);
}

long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> c){
	for(int i = 0; i < n; i++){
		R[i]++; c[i]++;
		int x = R[i] + c[i] - 1;
		a[x] = max(a[x], abs(R[i] - c[i]) + 1);
	}
	for(int i = 1; i < m * 2; i++){
		pref[i] = max(pref[i-1] - 1, a[i]);
	}
	for(int i = m * 2 - 1; i > 0; i--){
		suf[i] = max(suf[i+1] - 1, a[i]);
	}
	ll ans = 0;
	set<pll> mx;
	for(int i = 1; i < m * 2; i++){
		if(max(pref[i-1], suf[i+1]) <= a[i] && a[i]){
			v.push_back(i);
			// int p = v.size();
			// v.push_back(i);
			// l[p] = r[p] = p;
			// if(p){
			// 	ans -= get(v[p], v[p-1]);
			// 	mx.insert({f(p) , p});
			// }
			// ans += get(i, i);
		}
	}
	ans = get(v[0], v.back());
	r[0] = v.size()-1; l[v.size()-1] = 0;
	while(k--){
		ll mx = -1;
		vector<int> a;
		for(int i = 0; i < v.size(); i = r[i] + 1){
			for(int j =	i; j < r[i]; j++){
				ll x = get(v[i], v[r[i]]) - get(v[i], v[j]) - get(v[j+1], v[r[i]]) + get(v[j+1], v[j]);
				if(mx < x){
					mx = x;
					a = {i, j, j + 1, r[i]};
				}
			}
		}
		if(mx == -1) break;
		ans -= mx;
		r[a[0]] = a[1];
		l[a[1]] = a[0];
		r[a[2]] = a[3];
		l[a[3]] = a[2];
	}
	// for(int i = v.size(); i > k; i--){
	// 	pll num = *mx.begin();
	// 	mx.erase(num);
	// 	ans += num.first;
	// 	int b = num.second, a = l[b];
	// 	int c = b + 1, d = r[c];
	// 	if(a) mx.erase({f(a), a});
	// 	if(d + 1 < v.size()) mx.erase({f(d+1), d+1});
	// 	r[a] = d; l[d] = a;
	// 	if(a) mx.insert({f(a), a});
	// 	if(d + 1 < v.size()) mx.insert({f(d+1), d+1});
	// 	ll mn = (ll)1e18, p;
	// 	for(int i = 1; i < v.size(); i++){
	// 		if(l[i] == i && f(i) < mn){
	// 			mn = f(i);
	// 			p = i;
	// 		}
	// 	}
	// 	ans += mn;
	// 	r[l[p-1]] = r[p];
	// 	l[r[p]] = l[p-1];
	// }
	return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i = 0; i < v.size(); i = r[i] + 1){
      |                  ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40