Cod sursa(job #2244970)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 24 septembrie 2018 14:33:00
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("walls.in"); ofstream fout ("walls.out");

typedef long long i64;
const int nmax = 1e5;

int h[nmax + 1];
i64 term[nmax + 1];

struct Hsh {
    size_t operator ()(const pair<int, int> &shp) const {
        return shp.first + shp.second;
    }
};

unordered_map<pair<int, int>, i64, Hsh> mp;
vector<i64> xs;

int aint[4 * nmax + 1];

void build (int nod, int x, int y) {
    if (x == y) {
        aint[nod] = h[x];
        return ;
    }

    int mij = (x + y) / 2;
    build(2 * nod, x, mij);
    build(2 * nod + 1, mij + 1, y);
    aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}

void update (int nod, int x, int y, int pos, int val) {
    if (x == y) {
        aint[nod] = val;
        return ;
    }

    int mij = (x + y) / 2;
    if (pos <= mij)
        update(2 * nod, x, mij, pos, val);
    else
        update(2 * nod + 1, mij + 1, y, pos, val);

    aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}

int cauta (int nod, int x, int y, int lim, int val) {
    if (aint[nod] < val)
        return -1;

    if (x == y)
        return x;

    int mij = (x + y) / 2;
    int ans = -1;

    if (mij < lim) {
        ans = cauta(2 * nod + 1, mij + 1, y, lim, val);
    }

    if (ans == -1) {
        return cauta(2 * nod, x, mij, lim, val);
    }
    return ans;
}

int main () {
    int n, m;
    fin >> n;

    i64 pos_curr = 1;
    xs.push_back(0);
    for (int i = 1; i <= n; ++ i) {
        xs.push_back(pos_curr);
        int w;
        fin >> w >> h[i];

        term[i] = pos_curr + w - 1;
        pos_curr += w + 1;
    }

    build(1, 1, n);

    fin >> m;
    for (int nrt = 1; nrt <= m; ++ nrt) {
        i64 x;
        int y;
        fin >> x >> y;

        int trn = upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
        if (trn == 0) {
            fout << "MISS\n";
            continue;
        }

        int ind_lov = cauta(1, 1, n, trn, y);
        if (ind_lov == -1) {
            fout << "MISS\n";
            continue;
        }

        if (mp.find({ind_lov, y}) == mp.end()) {
            mp[{ind_lov, y}] = term[ind_lov];
        }

        fout << "HIT " << mp[{ind_lov, y}] << " " << ind_lov << " ";
        -- mp[{ind_lov, y}];

        if (mp[{ind_lov, y}] < xs[ind_lov]) {
            update(1, 1, n, ind_lov, y - 1);
            fout << "YES\n";
        } else {
            fout << "NO\n";
        }
    }

    fin.close();
    fout.close();
    return 0;
}