Submission #139851

#	Time	Username	Problem	Language	Result	Execution time	Memory
139851		SirCeness	Aliens (IOI16_aliens)	C++14	0 / 100	2025 ms	376 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000000000009
#define mod 1000000007
#define ppair(x) "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

vector<pair<int, int> > arr;

ll sq(int a, int b){
	if (a < b) return 0;
	return (ll)(a-b+1)*(ll)(a-b+1);
}

ll getcost(int a, int b){
	return sq(arr[b].x, arr[a].y) - sq(arr[a].x, arr[a].y) - sq(arr[b].x, arr[b].y) + sq(arr[a].x, arr[b].y);
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	vector<pair<int, int> > ekle1;
	for (int i = 0; i < n; i++) if (r[i] >= c[i]) ekle1.pb(mp(r[i], c[i]));
	else ekle1.pb(mp(c[i], r[i]));
	
	sort(ekle1.begin(), ekle1.end());
	for (int i = 0; i < n-1; i++){
		if (ekle1[i].first != ekle1[i+1].first && 
			ekle1[i].second != ekle1[i+1].second) arr.pb(ekle1[i]);
	}
	arr.pb(ekle1[n-1]);
	
	//for (int i = 0; i < arr.size(); i++) cout << ppair(arr[i]) << endl;
	
	ll ans = 0;
	for (int i = 0; i < arr.size(); i++){
		ans += sq(arr[i].x, arr[i].y);
		if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
	}
	
	set<pair<ll, int> > st;
	for (int i = 0; i < arr.size()-1; i++){
		ll cost = getcost(i, i+1);
		st.insert(mp(cost, i));
	}
	
	vector<int> bef(arr.size());
	for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
	bef[0] = -1;
	vector<int> nex(arr.size());
	for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
	nex[arr.size()-1] = -1;
	
	
	for (int q = 0; q < arr.size()-k; q++){
		//for (pair<ll, int> eleman: st) cout << ppair(eleman) << " "; cout << endl;
		int i = st.begin() -> second;
		ans += st.begin() -> first;
		int b = bef[i];
		int nx = nex[nex[i]];
		st.erase(st.begin());
		if (b != -1){
			ll costb = getcost(b, i);
			st.erase(st.find(mp(costb, b)));
		}
		if (nx != -1){
			ll costn = getcost(nex[i], nx);
			st.erase(st.find(mp(costn, nex[i])));
		}
		
		arr[i].x = arr[nex[i]].x;
		
		nex[i] = nx;
		if (nx != -1) bef[nx] = i;
		
		if (b != -1) st.insert(mp(getcost(b, i), b));
		if (nx != -1) st.insert(mp(getcost(i, nx), i));
		
	}
	
	
	
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); i++){
                  ~~^~~~~~~~~~~~
aliens.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i+1 != arr.size()) ans -= sq(arr[i].x, arr[i+1].y);
       ~~~~^~~~~~~~~~~~~
aliens.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++){
                  ~~^~~~~~~~~~~~~~
aliens.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < arr.size(); i++) bef[i] = i-1;
                  ~~^~~~~~~~~~~~
aliens.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size()-1; i++) nex[i] = i+1;
                  ~~^~~~~~~~~~~~~~
aliens.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int q = 0; q < arr.size()-k; q++){
                  ~~^~~~~~~~~~~~~~

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