Submission #867001

#	Time	Username	Problem	Language	Result	Execution time	Memory
867001		lolismek	Two Antennas (JOI19_antennas)	C++14	100 / 100	807 ms	40240 KiB

antennas

#include <iostream>
#include <vector>

#define pii pair <int, int>

using namespace std;

const int NMAX = 2e5;
const int INF = 1e9 + 10; // ?

int n, q;
int v[NMAX + 1];
pii ant[NMAX + 1];
pii quer[NMAX + 1];

vector <int> inds[NMAX + 1];
vector <pii> ev[NMAX + 1];

int qans[NMAX + 1];

namespace AINT{
    struct Node{
        int maxi, mini, diff;
    }seg[4 * NMAX + 1];

    void propag(int node, int l, int r){
        int x = seg[node].mini;
        seg[node].mini = +INF;
        // ^ singe-handedly the most important aspect of the Segment Tree
        // makes sure that a minimum finds a maximum, but not a maximum finds a minimum

        if(l < r){
            seg[2 * node].mini = min(seg[2 * node].mini, x);
            seg[2 * node].diff = max(seg[2 * node].diff, seg[2 * node].maxi - seg[2 * node].mini);

            seg[2 * node + 1].mini = min(seg[2 * node + 1].mini, x);
            seg[2 * node + 1].diff = max(seg[2 * node + 1].diff, seg[2 * node + 1].maxi - seg[2 * node + 1].mini);
        }
    }

    void build(int node, int l, int r){
        seg[node].maxi = -INF;
        seg[node].mini = +INF;
        seg[node].diff = seg[node].maxi - seg[node].mini;

        if(l == r){
            return;
        }

        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
    }

    void updatemx(int node, int l, int r, int pos, int val){
        propag(node, l, r);
        if(l == r){
            seg[node].maxi = val;
            seg[node].mini = +INF;
            seg[node].diff = max(seg[node].diff, seg[node].maxi - seg[node].mini);
            return;
        }

        int mid = (l + r) / 2;
        if(pos <= mid){
            updatemx(2 * node, l, mid, pos, val);
        }else{
            updatemx(2 * node + 1, mid + 1, r, pos, val);
        }

        propag(2 * node, l, mid);
        propag(2 * node + 1, mid + 1, r);

        seg[node].maxi = max(seg[2 * node].maxi, seg[2 * node + 1].maxi);
        seg[node].diff = max(seg[2 * node].diff, seg[2 * node + 1].diff);
    }

    void updatemn(int node, int l, int r, int ul, int ur, int val){
        propag(node, l, r);
        if(ul <= l && r <= ur){
            seg[node].mini = min(val, seg[node].mini);
            seg[node].diff = max(seg[node].diff, seg[node].maxi - seg[node].mini);
            return;
        }

        int mid = (l + r) / 2;
        if(ul <= mid){
            updatemn(2 * node, l, mid, ul, ur, val);
        }
        if(mid + 1 <= ur){
            updatemn(2 * node + 1, mid + 1, r, ul, ur, val);
        }

        propag(2 * node, l, mid);
        propag(2 * node + 1, mid + 1, r);

        seg[node].mini = max(seg[2 * node].mini, seg[2 * node + 1].mini);
        seg[node].diff = max(seg[2 * node].diff, seg[2 * node + 1].diff);
    }

    int query(int node, int l, int r, int ql, int qr){
        propag(node, l, r);
        if(ql <= l && r <= qr){
            return seg[node].diff;
        }

        int mid = (l + r) / 2, ans = -INF;
        if(ql <= mid){
            ans = max(ans, query(2 * node, l, mid, ql, qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans, query(2 * node + 1, mid + 1, r, ql, qr));
        }

        return ans;
    }

    int querym(int node, int l, int r, int ql, int qr){
        propag(node, l, r);
        if(ql <= l && r <= qr){
            return seg[node].maxi;
        }

        int mid = (l + r) / 2, ans = -INF;
        if(ql <= mid){
            ans = max(ans, querym(2 * node, l, mid, ql, qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans, querym(2 * node + 1, mid + 1, r, ql, qr));
        }

        return ans;
    }
}

void solve(){
    // clears
    for(int i = 1; i <= n; i++){
        ev[i].clear();
        inds[i].clear();
    }

    for(int i = 1; i <= n; i++){
        if(i + ant[i].first <= n){
            ev[i + ant[i].first].push_back({i, +1});
        }
        if(i + ant[i].second + 1 <= n){
            ev[i + ant[i].second + 1].push_back({i, -1});
        }
    }
    AINT::build(1, 1, n);

    for(int i = 1; i <= q; i++){
        inds[quer[i].second].push_back(i);
    }

    for(int i = 1; i <= n; i++){
        // process events
        for(pii e : ev[i]){
            if(e.second == +1){
                AINT::updatemx(1, 1, n, e.first, v[e.first]);
            }else{
                AINT::updatemx(1, 1, n, e.first, -INF);
            }
        }
        // update with current element
        if(i - ant[i].first >= 1){
            AINT::updatemn(1, 1, n, max(1, i - ant[i].second), i - ant[i].first, v[i]);
        }
        // answer queries
        for(int ind : inds[i]){
            qans[ind] = max(qans[ind], AINT::query(1, 1, n, quer[ind].first, quer[ind].second));
        }
    }
}

int main(){

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        cin >> ant[i].first >> ant[i].second;
    }

    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> quer[i].first >> quer[i].second;
        qans[i] = -1;
    }

    solve();

    // reverse
    for(int i = 1; i <= n / 2; i++){
        swap(v[i], v[n - i + 1]);
        swap(ant[i], ant[n - i + 1]);
    }
    for(int i = 1; i <= q; i++){
        quer[i].first = n - quer[i].first + 1;
        quer[i].second = n - quer[i].second + 1;
        swap(quer[i].first, quer[i].second);
    }

    solve();

    for(int i = 1; i <= q; i++){
        cout << qans[i] << '\n';
    }

    return 0;
}

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