oj.uz

답안 #796504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
796504 2023-07-28T12:58:00 Z thimote75 Two Antennas (JOI19_antennas) C++14
0 / 100
 3000 ms 27832 KB 
#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], - 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

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
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3038 ms 27832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -