Cod sursa(job #2892756)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 23 aprilie 2022 15:20:55
Problema Walls Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1e5;
int w[kN], h[kN];
unordered_map<int, int> hit[kN];

struct ST {
  int n;
  vector<int> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      t[x] = h[lx];
      return;
    }
    int mid = (lx + rx) / 2;
    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);
    t[x] = max(t[x * 2], t[x * 2 + 1]);
  }

  void update(int x, int lx, int rx, int pos) {
    if (lx == rx) {
      t[x] = h[pos];
      return;
    }
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      update(x * 2, lx, mid, pos);
    } else {
      update(x * 2 + 1, mid + 1, rx, pos);
    }
    t[x] = max(t[x * 2], t[x * 2 + 1]);
  }

  void update(int pos) {
    update(1, 0, n - 1, pos);
  }

  int query(int x, int lx, int rx, int pref, int ht) {
    if (lx == rx) {
      if (ht <= t[x]) {
        return lx;
      }
      return -1;
    }
    int mid = (lx + rx) / 2;
    if (mid < pref && ht <= t[x * 2 + 1]) {
      int ret = query(x * 2 + 1, mid + 1, rx, pref, ht);
      if (ret != -1) {
        return ret;
      }
    }
    return query(x * 2, lx, mid, pref, ht);
  }

  int query(int pref, int ht) {
    return query(1, 0, n - 1, pref, ht);
  }
};

void testCase() {
  int n;
  fin >> n;
  vector<int64_t> len(n);
  for (int i = 0; i < n; ++i) {
    fin >> w[i] >> h[i];
    len[i] = w[i] + 1;
    if (i) {
      len[i] += len[i - 1];
    }
  }
  ST t(n);
  t.build(1, 0, n - 1);
  int q;
  fin >> q;
  for (int i = 0; i < q; ++i) {
    int x, y;
    fin >> x >> y;
    int pref = distance(len.begin(), upper_bound(len.begin(), len.end(), x)) - 1;
    if (pref == -1) {
      fout << "MISS\n";
      continue;
    }
    int pos = t.query(pref, y);
    if (pos == -1) {
      fout << "MISS\n";
      continue;
    }
    fout << "HIT " << len[pos] - 1 - hit[pos][y] << ' ' << pos + 1;
    hit[pos][y] += 1;
    if (hit[pos][y] == w[pos]) {
      h[pos] = y - 1;
      t.update(pos);
      fout << " YES\n";
    } else {
      fout << " NO\n";
    }
  }
}

int main() {
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  fin.close();
  fout.close();
  return 0;
}