Cod sursa(job #1551936)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 16 decembrie 2015 22:09:18
Problema Walls Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;

class max_arbint_cu_cautare{
	int n;
	vector<int> buf;
public:
	template <typename T, typename Conv>
	max_arbint_cu_cautare(const vector<T>& v, Conv c): n(v.size()), buf(2*n){
		for(int i = 0; i < n; ++i){
			buf[i+n] = c(v[i]); }
		for(int i = n-1; i > 0; --i){
			buf[i] = max(buf[2*i], buf[2*i+1]); } }
	int cauta(int st, int dr, const int val){
		if(st == -1){
			return -1; }
		int rad_st = -1, rad_dr = -1;
		for(st += n, dr += n+1; st < dr; st /= 2, dr /= 2){
			if(st%2 == 1){
				if(buf[st] >= val){
					rad_st = st; }
				++st; }
			if(dr%2 == 1){
				--dr;
				if(buf[dr] >= val && rad_dr == -1){
					rad_st = dr; } } }
		int rad = (rad_st == -1 ? rad_dr : rad_st);
		if(rad == -1){
			return -1; }
		while(rad < n){
			if(buf[2*rad+1] >= val){
				rad = 2*rad+1; }
			else{
				rad = 2*rad; } }
		return rad-n; }
	void update(int poz, const int val){
		for(buf[poz+=n] = val; poz > 1; poz /= 2){
			buf[poz/2] = max(buf[poz], buf[poz^1]); } } };

struct perete{
	int x, w, h;
	unordered_map<int, int> scoase;
	int poz_atack(const int att_h){
		return x + w - 1 - scoase[att_h]; }
	bool attack(const int att_h){
		++scoase[att_h];
		if(scoase[att_h] >= w){
			h = att_h-1;
			return true; }
		return false; } };

bool operator<(const perete& a, const perete& b){
	return a.x < b.x; }

bool operator<(const perete& a, const int b){
	return a.x < b; }

bool operator<(const int a, const perete& b){
	return a < b.x; }

int main(){
	ifstream f("walls.in");
	ofstream g("walls.out");
	int n;
	f >> n;

	vector<perete> pereti(n);
	{
		int x_cur = 1;
		for(auto& x : pereti){
			f >> x.w >> x.h;
			x.x = x_cur;
			x_cur += x.w+1; } }

	max_arbint_cu_cautare mac(pereti, [](const perete& p){
		return p.h; });

	int m;
	f >> m;
	for(int i = 0, x, y; i < m; ++i){
		f >> x >> y;
		const int poz = (upper_bound(pereti.begin(), pereti.end(), x) - pereti.begin()) - 1;
		const int which = mac.cauta(0, poz, y);
		if(which == -1){
			g << "MISS\n";
			continue; }
		const int x_att = pereti[which].poz_atack(y);
		const bool prabusit = pereti[which].attack(y);
		if(prabusit){
			mac.update(which, pereti[which].h); }
		g << "HIT " << x_att << ' ' << (which+1) << ' ' << (prabusit ? "YES\n" : "NO\n"); }
	return 0; }