Cod sursa(job #2460973)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 24 septembrie 2019 19:17:02
Problema Walls Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <fstream>
#include <set>
#define ub(x) (x&(-x))

using namespace std;

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

constexpr int NMAX = 1e5 + 5;

int n, m;

long long sumw[NMAX];
int h[NMAX];
int w[NMAX];
int arb[2*NMAX];

multiset <int> S[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 <= a && b <= qb) return arb[nod];

    int mij = (a + b) / 2;
    int r1=0, r2=0;

    if (qa <= mij) r1=query(2*nod, a, mij, qa, qb);
    if (mij < qb) r2=query(2*nod+1, mij+1, b, qa, qb);

    return max(r1, r2);
}

int cautbin_w (int val)
{
    int st=1;
    int dr=n;
    int poz=0;

    while (st <= dr)
    {
        int mij = (st + dr) >> 1;

        if (sumw[mij] > val) dr=mij-1;
        else if (sumw[mij] <= val)
        {
            st = mij + 1;
            poz = mij;
        }
    }

    return poz;
}

bool verif (int poz, int val)
{
    if (query(1, 1, n, 1, poz) >= val) return true;

    return false;
}

int cautbin_wall (int val, int pozMaxWall)
{
    int st = 1;
    int dr = pozMaxWall;
    int poz = 0;

    while (st <= dr)
    {
        int mij = (st + dr) / 2;

        if (query(1, 1, n, mij, pozMaxWall) >= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    return poz;
}

int main()
{
    f >> n;

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

    for (int i=1; i<=n; ++i)
        update(1, 1, n, i, h[i]);

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

    f >> m;

    for (int i=1; i<=m; ++i)
    {
        int x, y;
        f >> x >> y;

        int pozMaxWall = cautbin_w(x);
        bool hit = verif(pozMaxWall, y);

        if (!hit)
        {
            g << "MISS\n";
            continue;
        }
        g << "HIT ";

        int wall = cautbin_wall(y, pozMaxWall);
        int gigel = S[wall].count(y);

        g << sumw[wall] - gigel << " " << wall << " ";

        S[wall].insert(y);
        gigel++;

        if (gigel == w[wall])
        {
            h[wall] = y-1;
            update(1, 1, n, wall, h[wall]);
            g << "YES" << '\n';
        }
        else g << "NO" << '\n';

    }
    return 0;
}