Submission #1106052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106052		nhanhoang510	Two Antennas (JOI19_antennas)	C++14	100 / 100	551 ms	45640 KiB

antennas

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2 * 1e5 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

struct SegTree{
    int size;
    vector<int> maxs;
    vector<ii> oper_value;
    vector<ii> on_value;

    void init(int n){
        size = n;
        maxs.assign(n * 4 + 7, -1);
        oper_value.assign(n * 4 + 7, {-1, -1});
        on_value.assign(n * 4 + 7, {-1, -1});
        return;
    }

    int get_value(ii a, ii b){
        if(a.F == -1 || b.F == -1)
            return -1;
        int res = abs(a.F - b.F);
        res = max(res, abs(a.F - b.S));
        res = max(res, abs(a.S - b.F));
        res = max(res, abs(a.S - b.S));
        return res;
    }

    ii Union(ii a, ii b){
        if(a.F == -1 && b.F == -1)
            return a;
        if(a.F == -1)
            return b;
        if(b.F == -1)
            return a;
        ii c = {min(a.F, b.F), max(a.S, b.S)};
        return c;
    }

    void propagate(int id, int l, int r){
        if(l == r){
            oper_value[id] = {-1, -1};
            return;
        }
        if(oper_value[id].F == -1)
            return;

        maxs[id * 2] = max(maxs[id * 2], get_value(oper_value[id], on_value[id * 2]));
        oper_value[id * 2] = Union(oper_value[id * 2], oper_value[id]);
        maxs[id * 2 + 1] = max(maxs[id * 2 + 1], get_value(oper_value[id], on_value[id * 2 + 1]));
        oper_value[id * 2 + 1] = Union(oper_value[id * 2 + 1], oper_value[id]);

        oper_value[id] = {-1, -1};
        return;
    }

    void update(int id, int l, int r, int u, int v, int val){
        propagate(id, l, r);
        if(v < l || u > r)
            return;
        if(u <= l && r <= v){
            maxs[id] = max(maxs[id], get_value(on_value[id], {val, val}));
            oper_value[id] = Union(oper_value[id], {val, val});
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);
        maxs[id] = max(maxs[id * 2], maxs[id * 2 + 1]);
        return;
    }

    void update(int l, int r, int val){
        update(1, 1, size, l, r, val);
        return;
    }

    void update_change(int id, int l, int r, int u, int val){
        propagate(id, l, r);
        if(u < l || u > r)
            return;
        if(l == r){
            on_value[id] = {val, val};
            return;
        }
        int mid = (l + r) / 2;
        update_change(id * 2, l, mid, u, val);
        update_change(id * 2 + 1, mid + 1, r, u, val);
        on_value[id] = Union(on_value[id * 2], on_value[id * 2 + 1]);
        return;
    }

    void update_change(int id, int val){
        update_change(1, 1, size, id, val);
        return;
    }

    int get_max(int id, int l, int r, int u, int v){
        propagate(id, l, r);
        if(v < l || u > r)
            return -1;
        if(u <= l && r <= v)
            return maxs[id];
        int mid = (l + r) / 2;
        return max(get_max(id * 2, l, mid, u, v), get_max(id * 2 + 1, mid + 1, r, u, v));
    }

    int get_max(int l, int r){
        return get_max(1, 1, size, l, r);
    }
};

int n, q;

int h[maxn];

int a[maxn];
int b[maxn];

ii queries[maxn];

int ans[maxn];

vector<int> query_answer[maxn];
vector<ii> query_change[maxn];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> h[i] >> a[i] >> b[i];
    }
    cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> queries[i].F >> queries[i].S;
    }

    // INIT QUERY - ANS
    memset(ans, -1, sizeof(ans));
    for(int i = 1; i <= q; ++i){
        int l = queries[i].F;
        int r = queries[i].S;
        query_answer[r].push_back(i);
    }
    for(int i = 1; i <= n; ++i) if(i + a[i] <= n){
        query_change[i + a[i]].push_back({i, +h[i]});
        if(i + b[i] + 1 <= n)
            query_change[i + b[i] + 1].push_back({i, -1});
    }
    SegTree st;
    st.init(n);


    for(int i = 1; i <= n; ++i){
        for(ii change : query_change[i]){
            int pos = change.F;
            int val = change.S;
            st.update_change(pos, val);
        }
        int L = max(1, i - b[i]);
        int R = i - a[i];
        if(1 <= R)
            st.update(L, R, +h[i]);

        for(int id : query_answer[i]){
            int l = queries[id].F;
            ans[id] = st.get_max(l, i);
        }
    }

    for(int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:155:13: warning: unused variable 'l' [-Wunused-variable]
  155 |         int l = queries[i].F;
      |             ^

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