Cod sursa(job #2462828)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 27 septembrie 2019 21:03:56
Problema Walls Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <map>

using namespace std;

ifstream f ("walls.in");
ofstream g ("walls.out");

constexpr int NMAX = 1e5 + 5;

int n, m;

int sumw[NMAX];
int h[NMAX];
int w[NMAX];
int arb[4*NMAX];

map <int, int> fr[NMAX];

void update (int nod, int a, int b, int poz, int val)
{
    if (a == b)
    {
        arb[nod] = val;
        return;
    }
    int mij = (a+b)/2;

    if (poz <= mij) update(2*nod, a, mij, poz, val);
    else update(2*nod+1, mij+1, b, poz, val);

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

int query (int nod, int a, int b, int qa, int qb)
{
    if (qa < sumw[a] || qb > arb[nod] || a > b) return -1;

    if (a == b) return a;

    int mij = (a + b) / 2;
    int rez = 0;

    rez = query(2*nod+1, mij+1, b, qa, qb);
    if (rez == -1) rez = query(2*nod, a, mij, qa, qb);

    return rez;
}

int main()
{
    f >> n;

    for (int i=1; i<=n; ++i)
    {
        f >> w[i] >> h[i];
        update(1, 1, n, i, h[i]);
    }

    sumw[1] = 1;

    for (int i=2; i<=n; ++i)
        sumw[i] = sumw[i-1] + w[i-1] + 1;

    f >> m;

    for (; m; --m)
    {
        int poz, in;
        f >> poz >> in;

        int poshit = query(1, 1, n, poz, in);

        if (poshit == -1)
        {
            g << "MISS\n";
            continue;
        }

        g << "HIT ";
        g << sumw[poshit] + w[poshit] - 1 - fr[poshit][in] << " " << poshit << " ";

        fr[poshit][in]++;

        if (fr[poshit][in] == w[poshit])
        {
            update(1, 1, n, poshit, in-1);
            g << "YES\n";
        }
        else g << "NO\n";
    }
    return 0;
}