Submission #1022024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022024		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	452 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.rbegin();
		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});
	}
	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:60:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if(d + 1 < v.size()) mx.erase({f(d+1), d+1});
      |      ~~~~~~^~~~~~~~~~
aliens.cpp:63:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if(d + 1 < v.size()) mx.insert({f(d+1), d+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