Submission #1022034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022034		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	348 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]){
			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);
		}
	}
	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:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i = 1; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
aliens.cpp:72:18: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |   r[l[p-1]] = r[p];
      |               ~~~^

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