Submission #796514

#	Time	Username	Problem	Language	Result	Execution time	Memory
796514		thimote75	Two Antennas (JOI19_antennas)	C++14	13 / 100	3020 ms	27764 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
using vEvents = vector<pair<int, pair<int, int>>>;

struct LazySegTree {
    vector<int> max_array;
    vector<int> del;

    LazySegTree () = default;
    LazySegTree (int size) {
        max_array.resize(size, 0);
        del.resize(size, - 1e9);
    }

    void update (int l, int r, int mx) {
        if (r < 0) return ;
        if (l < 0) l = 0;

        for (int i = l; i <= r; i ++)
            max_array[i] = max(max_array[i], mx);
    }
    void set (int index, int mx, int delta) {
        max_array[index] = mx;
        del[index] = delta;
    }
    int query (int l, int r) {
        int res = -1e9;
        for (int i = l; i <= r; i ++)
            res = max(res, max_array[i] + del[i]);
        return res;
    }
    int get (int i) {
        return max_array[i] + del[i];
    }
};

struct QueryManager {
    idata A, B, H;
    vEvents events;
    int iEv = 0;

    LazySegTree s_prov;
    LazySegTree s_fina;

    int right = -1;

    QueryManager (idata _A, idata _B, idata _H) {
        A = _A; B = _B; H = _H;

        s_prov = LazySegTree(A.size());
        s_fina = LazySegTree(A.size());

        for (int i = 0; i < A.size(); i ++) {
            events.push_back({ i + A[i],     { i, 0 } });
            events.push_back({ i + B[i] + 1, { i, 1 } });
        }

        sort(events.begin(), events.end());
    }

    void increase () {
        right ++;

        while (iEv != events.size() && events[iEv].first == right) {
            const auto event = events[iEv]; iEv ++;

            int id = event.second.first;
            int ty = event.second.second;

            if (ty == 0) {
                s_prov.set(id, H[id] - 1, - H[id]);
            } else if (ty == 1) {
                int loc = s_prov.get(id);
                s_prov.set(id, 0, - 1e9);
                s_fina.set(id, loc, 0);
            }
        }

        s_prov.update(right - B[right], right - A[right], H[right]);
    }
    void update (int target) {
        while (right < target) increase();
    }

    int query (int qleft, int qright) {
        update(qright);

        return max(s_prov.query(qleft, qright), s_fina.query(qleft, qright));
    }
};

int main () {
    int N;
    cin >> N;

    idata H(N), A(N), B(N);
    for (int i = 0; i < N; i ++)
        cin >> H[i] >> A[i] >> B[i];
    
    QueryManager table_pos(A, B, H);
    for (int i = 0; i < N; i ++)
        H[i] *= -1;
    QueryManager table_neg(A, B, H);

    int Q; cin >> Q;
    vector<pair<pair<int, int>, int>> queries;
    idata answers(Q);
    for (int q = 0; q < Q; q ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        queries.push_back({ {b, a}, q });
    }

    sort(queries.begin(), queries.end());

    for (const auto &query : queries) {
        answers[query.second] = max(
            table_pos.query( query.first.second, query.first.first ),
            table_neg.query( query.first.second, query.first.first )
        );
        if (answers[query.second] < 0) answers[query.second] = -1;
    }

    for (int u : answers) cout << u << "\n";
}

Compilation message (stderr)

antennas.cpp: In constructor 'QueryManager::QueryManager(idata, idata, idata)':
antennas.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < A.size(); i ++) {
      |                         ~~^~~~~~~~~~
antennas.cpp: In member function 'void QueryManager::increase()':
antennas.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while (iEv != events.size() && events[iEv].first == right) {
      |                ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65