Pagini recente » Cod sursa (job #71543) | Cod sursa (job #3150252) | Cod sursa (job #722840) | Istoria paginii utilizator/georgia29 | Cod sursa (job #1551940)
#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(dr == -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_dr = dr; } } }
int rad = (rad_dr == -1 ? rad_st : rad_dr);
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; }