Submission #1266695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266695		ducanh0811	Two Antennas (JOI19_antennas)	C++20	100 / 100	487 ms	48268 KiB

antennas

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 200005
const int INF = 1e16;
int n, q, h[MAXN], a[MAXN], b[MAXN];
vector<int> ok[MAXN];
vector<pair<int, int>> query[MAXN];
pair<int, int> save[MAXN];
int res[MAXN];

struct SMT {
    int n;
    vector<int> st, ts, lz;
    SMT(int _n = 0){
        n = _n;
        st.assign((n << 2) + 5, +INF);
        ts.assign((n << 2) + 5, -INF);
        lz.assign((n << 2) + 5, -INF);
    }

    void update(int id, int l, int r, int p, int val) {
        if (l == r) return st[id] = val, void();
        int mid = (l + r) >> 1;
        push(id);
        if (p <= mid) update(id << 1, l, mid, p, val);
            else update(id << 1 | 1, mid + 1, r, p, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }
    void update(int p, int val){
        update(1, 1, n, p, val);
    }

    void push(int id){
        if (lz[id] == -INF) return;
        lz[id << 1] = max(lz[id << 1], lz[id]);
        lz[id << 1 | 1] = max(lz[id << 1 | 1], lz[id]);
        ts[id << 1] = max(ts[id << 1], lz[id] - st[id << 1]);
        ts[id << 1 | 1] = max(ts[id << 1 | 1], lz[id] - st[id << 1 | 1]);
        lz[id] = -INF;
    }

    void updateRange(int id, int l, int r, int u, int v, int val) {
        if (v < l || r < u) return;
        if (u <= l && r <= v){
            ts[id] = max(ts[id], val - st[id]);
            lz[id] = max(lz[id], val);
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        updateRange(id << 1, l, mid, u, v, val);
        updateRange(id << 1 | 1, mid + 1, r, u, v, val);
        ts[id] = max(ts[id << 1], ts[id << 1 | 1]);
    }
    void updateRange(int u, int v, int val) {
        updateRange(1, 1, n, u, v, val);
    }

    int get(int id, int l, int r, int u, int v) {
        if (v < l || r < u) return -INF;
        if (u <= l && r <= v) return ts[id];
        int mid = (l + r) >> 1;
        push(id);
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    int get(int u, int v) {
        return get(1, 1, n, u, v);
    }
};

int M(int x){
    x = min(n, x);
    x = max(x, 1ll);
    return x;
}

void process(){
    SMT tree = SMT(n);
    FOR(i, 1, n){
        for (int &x : ok[i]){
            if (x > 0){
                tree.update(+x, h[x]);
            } else {
                tree.update(-x, INF);
            }
        }
        if (i - a[i] > 0) tree.updateRange(M(i - b[i]), M(i - a[i]), h[i]);
        for (pair<int, int> &x : query[i]){
            res[x.second] = max(res[x.second], tree.get(x.first, i));
        }
    }
}

void solve(){
    cin >> n;
    FOR(i, 1, n){
        cin >> h[i] >> a[i] >> b[i];
        ok[min(n + 1, i + a[i])].push_back(i);
        ok[min(n + 1, i + b[i] + 1)].push_back(-i);
    }
    cin >> q;
    FOR(i, 1, q){
        int l, r; cin >> l >> r;
        res[i] = -1;
        save[i] = make_pair(l, r);
        query[r].push_back(make_pair(l, i));
    }
    process();
    FOR(i, 1, n) h[i] *= -1;
    process();
    FOR(i, 1, q){
        cout << res[i] << '\n';
    }
}

#define task ""
int32_t main(){
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

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

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