Cod sursa(job #1759804)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 19 septembrie 2016 20:57:25
Problema Walls Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <queue>
#include <map>
#include <set>

using namespace std;

ifstream cin("walls.in");
ofstream cout("walls.out");

const int MAXN = 100000;

int width[1 + MAXN], height[1 + MAXN];
long long sum[1 + MAXN];
int tree[1 + 4 * MAXN];

void Update(int node, int left, int right, int index) {
    if (left == right) {
        tree[node] = left;
        return;
    }
    int middle = (left + right) / 2;
    if (index <= middle)
        Update(2 * node, left, middle, index);
    else
        Update(2 * node + 1, middle + 1, right, index);
    if (height[tree[2 * node + 1]] < height[tree[2 * node]])
        tree[node] = tree[2 * node];
    else
        tree[node] = tree[2 * node + 1];
}

int BinarySearch(int value, int n) {
    int left = 1, right = n, answer = 0;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (sum[middle] <= value) {
            answer = middle;
            left = middle + 1;
        }
        else
            right = middle - 1;
    }
    return answer;
}

int Query(int node, int left, int right, int index, int target) {
    if (left > index)
        return -1;
    if (right <= index) {
        if (height[tree[node]] < target)
            return -1;
        if (left == right)
            return tree[node];
    }
    int middle = (left + right) / 2;
    int answer = Query(2 * node + 1, middle + 1, right, index, target);
    if (answer != -1)
        return answer;
    return Query(2 * node, left, middle, index, target);
}

map<pair<int, int>, int> table;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> width[i] >> height[i];
        sum[i] = sum[i - 1] + width[i] + 1;
        Update(1, 1, n, i);
    }
    int tests;
    cin >> tests;
    for (int test = 1; test <= tests; test++) {
        int x, y;
        cin >> x >> y;
        int answer = Query(1, 1, n, BinarySearch(x + 1, n), y);
        if (answer == -1) {
            cout << "MISS\n";
            continue;
        }
        cout << "HIT ";
        table[make_pair(answer, y)]++;
        int where = table[make_pair(answer, y)];
        cout << sum[answer] - where << " " << answer << " ";
        if (where == width[answer]) {
            height[answer] = y - 1;
            Update(1, 1, n, where);
            cout << "YES\n";
        }
        else
            cout << "NO\n";
    }
    return 0;
}