Submission #1108235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108235		Zero_OP	Two Antennas (JOI19_antennas)	C++14	100 / 100	355 ms	49640 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 7;

struct SegmentTree{
    struct info{
        int best, mx, mn, lazy_min, lazy_max;

        info() : best(-1), mx(-inf), mn(+inf), lazy_max(-inf), lazy_min(+inf) {}
    };

    vector<info> st;
    SegmentTree(int n) : st(n << 2) {}

    void apply(int id, int mx, int mn){
        st[id].best = max(st[id].best, mx - st[id].mn);
        st[id].best = max(st[id].best, st[id].mx - mn);
        st[id].lazy_max = max(st[id].lazy_max, mx);
        st[id].lazy_min = min(st[id].lazy_min, mn);
    }

    void pull(int id){
        st[id].best = max(st[id << 1].best, st[id << 1 | 1].best);
        st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx);
        st[id].mn = min(st[id << 1].mn, st[id << 1 | 1].mn);
    }

    void propagate(int id){
        apply(id << 1, st[id].lazy_max, st[id].lazy_min);
        apply(id << 1 | 1, st[id].lazy_max, st[id].lazy_min);
        st[id].lazy_max = -inf;
        st[id].lazy_min = +inf;
    }

    void point_update(int id, int l, int r, int pos, int val){
        if(l == r){
            if(val == -1) st[id].mx = -inf, st[id].mn = +inf;
            else st[id].mx = st[id].mn = val;
        } else{
            int mid = l + r >> 1;
            propagate(id);
            if(pos <= mid) point_update(id << 1, l, mid, pos, val);
            else point_update(id << 1 | 1, mid + 1, r, pos, val);
            pull(id);
        }
    }

    void update(int id, int l, int r, int u, int v, int val){
        if(u <= l && r <= v){
            apply(id, val, val);
        } else{
            int mid = l + r >> 1;
            propagate(id);
            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
            pull(id);
        }
    }

    int query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return -1;
        if(u <= l && r <= v) return st[id].best;
        int mid = l + r >> 1;
        propagate(id);
        return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N;
    cin >> N;
    vector<int> H(N), A(N), B(N);
    for(int i = 0; i < N; ++i){
        cin >> H[i] >> A[i] >> B[i];
    }

    int Q;
    cin >> Q;
    vector<int> answer(Q, -1);
    vector<vector<pair<int, int>>> queries(N);
    for(int i = 0; i < Q; ++i){
        int L, R;
        cin >> L >> R;
        --L, --R;
        queries[R].emplace_back(L, i);
    }

    vector<vector<int>> in(N), out(N);
    for(int i = 0; i < N; ++i){
        if(i + A[i] < N) in[i + A[i]].push_back(i);
        if(i + B[i] < N) out[i + B[i]].push_back(i);
    }

    SegmentTree T(N);
    for(int i = 0; i < N; ++i){
        for(int pos : in[i]){
            T.point_update(1, 0, N - 1, pos, H[pos]);
        }

        if(i - A[i] >= 0){
            T.update(1, 0, N - 1, max(0, i - B[i]), i - A[i], H[i]);
        }

        for(auto [j, id] : queries[i]){
            answer[id] = T.query(1, 0, N - 1, j, i);
        }

        for(int pos : out[i]){
            T.point_update(1, 0, N - 1, pos, -1);
        }
    }

    for(int i = 0; i < Q; ++i){
        cout << answer[i] << '\n';
    }
}

Compilation message (stderr)

antennas.cpp: In constructor 'SegmentTree::info::info()':
antennas.cpp:9:37: warning: 'SegmentTree::info::lazy_max' will be initialized after [-Wreorder]
    9 |         int best, mx, mn, lazy_min, lazy_max;
      |                                     ^~~~~~~~
antennas.cpp:9:27: warning:   'int SegmentTree::info::lazy_min' [-Wreorder]
    9 |         int best, mx, mn, lazy_min, lazy_max;
      |                           ^~~~~~~~
antennas.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         info() : best(-1), mx(-inf), mn(+inf), lazy_max(-inf), lazy_min(+inf) {}
      |         ^~~~
antennas.cpp: In member function 'void SegmentTree::point_update(int, int, int, int, int)':
antennas.cpp:42:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             int mid = l + r >> 1;
      |                       ~~^~~
antennas.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
antennas.cpp:54:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |             int mid = l + r >> 1;
      |                       ~~^~~
antennas.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
antennas.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = l + r >> 1;
      |                   ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:114:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |         for(auto [j, id] : queries[i]){
      |                  ^

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