Submission #57841

#	Time	Username	Problem	Language	Result	Execution time	Memory
57841		robert	Aliens (IOI16_aliens)	C++14	0 / 100	4 ms	488 KiB

aliens

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <queue>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
vector<int> rng;

map<int, int> v;
vi seg;

int mv(int l, int r){
	if(v[rng[l]]<v[rng[r]])
		return r;
	else
		return l;
}

int build(int L, int R, int p){
	if(L==R)
		return seg[p] = rng[L];
	else
		return seg[p] = mv(build(L, (L+R)/2, p*2), build((L+R)/2+1, R, p*2+1));
}

int qr(int l, int r, int L, int R, int p){
	if(L>=l&&R<=r)
		return seg[p];
	else if(L>r||R<l)
		return seg.size();
	else {
		int l = qr(l, r, L, (L+R)/2, p*2);
		int r = qr(l, r, (L+R)/2+1, R, p*2+1);
		if(l>1e8)
			return r;
		else if(r>1e8)
			return r;
		if(v[rng[l]]<v[rng[r]])
			return r;
		else
			return l;
	}
}

long long pow(int n, int a){
	if(a==0){
		return n;
	} else{
		if(1&a){
			return pow(n, a-1);
		} else{
			return pow(n, a>>2);
		}
	}
}

long long take_photos(int n, int m, int k, vector<int> r, vi c){
	for(int x=0; x<n; x++){
		if(r[x]>c[x])
			swap(c[x], r[x]);
		v[r[x]] = max(v[r[x]], c[x]);
	}
	int minx = 1e9, maxx=0;
	
	for(auto x:v){
		minx = min(minx, x.first);
		maxx = max(maxx, x.first);
		cout << x.first << " " << x.second << endl;
		rng.push_back(x.first);
	}
	seg.assign(4*rng.size(), 0);
	build(1, rng.size(), 1);
	priority_queue<pair<int, ii>> p;
	p.push({pow(qr(1, rng.size(), 1, rng.size(), 1), 2)-pow(rng[rng.size()-1]-rng[0], 2), {1, rng.size()}});
	while(!p.empty()&&k>0){
		pair<int, ii> t = p.top(); p.pop();

		k--;
	}
	return 0;
}
/*
int main(){
	vi r{0, 4, 4, 4, 4}, c = {3, 4, 6, 5, 6};
	cout << take_photos(5, 7, 2, r, c) << endl;
	return 0;
}*/

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, vi)':
aliens.cpp:80:17: warning: variable 't' set but not used [-Wunused-but-set-variable]
   pair<int, ii> t = p.top(); p.pop();
                 ^
aliens.cpp: In function 'int qr(int, int, int, int, int)':
aliens.cpp:36:35: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int l = qr(l, r, L, (L+R)/2, p*2);
                                   ^
aliens.cpp:37:39: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int r = qr(l, r, (L+R)/2+1, R, p*2+1);
                                       ^

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