Submission #1287296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287296		dex111222333444555	Two Antennas (JOI19_antennas)	C++17	0 / 100	318 ms	90636 KiB

antennas

#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define fi first
#define se second
#define ii pair<int, int>
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 2e5 + 5, infINT = 1e9 + 373;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numVal, numQuery, height[MAXN], minRange[MAXN], maxRange[MAXN], res[MAXN];
vector<ii> query[MAXN], events[MAXN];

struct segmentTree{
    struct Node{
        int minVal, maxVal, maxDiff;
        Node(int _minVal = infINT, int _maxVal = -infINT, int _maxDiff = -infINT):
            minVal(_minVal), maxVal(_maxVal), maxDiff(_maxDiff) {};
    };

    int n;
    vector<Node> node, lazy;

    segmentTree(int _n = 0): n(_n){
        node.assign(n << 4 | 1, Node());
        lazy.assign(n << 4 | 1, Node());
    }

    Node combine(const Node &left, const Node &right){
        Node mid;
        mid.minVal = min(left.minVal, right.minVal);
        mid.maxVal = max(left.maxVal, right.maxVal);
        mid.maxDiff = max(left.maxDiff, right.maxDiff);
        return mid;
    }

    void push(int id, int l, int r){
        if (l > r) return;
        if (lazy[id].minVal == infINT && lazy[id].maxVal == -infINT) return;
        maximize(node[id].maxDiff, node[id].maxVal - lazy[id].minVal);
        maximize(node[id].maxDiff, lazy[id].maxVal - node[id].minVal);
        if (l != r){
            for(int nid = 2 * id; nid <= 2 * id + 1; nid++){
                minimize(lazy[nid].minVal, lazy[id].minVal),
                maximize(lazy[nid].maxVal, lazy[id].maxVal);
            }
        }
        lazy[id] = Node();
    }

    void down(int id, int l, int r){
        int m = (l + r) >> 1;
        push(id << 1, l, m);
        push(id << 1 | 1, m + 1, r);
    }

    void updatePoint(int id, int l, int r, int pos, int minVal, int maxVal){
        down(id, l, r);
        if (l == r){
            node[id].minVal = minVal;
            node[id].maxVal = maxVal;
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) updatePoint(id << 1, l, m, pos, minVal, maxVal);
        else updatePoint(id << 1 | 1, m + 1, r, pos, minVal, maxVal);
        node[id] = combine(node[id << 1], node[id << 1 | 1]);
    }

    void updatePoint(int pos, int minVal, int maxVal){
        updatePoint(1, 1, n, pos, minVal, maxVal);
    }

    void updateRange(int id, int l, int r, int u, int v, int val){
        down(id, l, r);
        if (l > r || l > v || r < u || u > v) return;
        if (l >= u && r <= v){
            minimize(lazy[id].minVal, val);
            maximize(lazy[id].maxVal, val);
            down(id, l, r);
            return;
        }
        int m = (l + r) >> 1;
        updateRange(id << 1, l, m, u, v, val);
        updateRange(id << 1 | 1, m + 1, r, u, v, val);
        node[id] = combine(node[id << 1], node[id << 1 | 1]);
    }

    void updateRange(int u, int v, int val){
        updateRange(1, 1, n, u, v, val);
    }

    Node get(int id, int l, int r, int u, int v){
        down(id, l, r);
        if (l > r || l > v || r < u || u > v) return Node();
        if (l >= u && r <= v) return node[id];
        int m = (l + r) >> 1;
        return combine(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }

    int get(int u, int v){
        Node tmp = get(1, 1, n, u, v);
        return tmp.maxDiff;
    }

};

void input(){
    cin >> numVal;
    for(int i = 1; i <= numVal; i++){
        cin >> height[i] >> minRange[i] >> maxRange[i];
        if (i + minRange[i] <= numVal)
            events[i + minRange[i]].push_back({i, +1});
        if (i + maxRange[i] + 1 <= numVal)
            events[i + maxRange[i] + 1].push_back({i, -1});
    }
    cin >> numQuery;
    for(int q = 1; q <= numQuery; q++){
        int L, R; cin >> L >> R;
        query[R].push_back({L, q});
    }
}

void solve(){
    segmentTree myIt(numVal);
    for(int pos = 1; pos <= numVal; pos++){
        for(pair<int, int> change: events[pos]){
            int id = change.fi, type = change.se;
            if (type == +1) myIt.updatePoint(id, height[id], height[id]);
            if (type == -1) myIt.updatePoint(id, infINT, -infINT);
        }
        int L = max(1, pos - maxRange[pos]);
        int R = pos - minRange[pos];
        if (L <= R){
            myIt.updateRange(L, R, height[pos]);
        }
        for(pair<int, int> answer: query[pos]){
            int L = answer.fi, R = pos, id = answer.se;
            res[id] = -1;
            maximize(res[id], myIt.get(L, R));
        }
    }
    for(int q = 1; q <= numQuery; q++) cout << res[q] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    input();
    solve();
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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