Submission #866969

#	Time	Username	Problem	Language	Result	Execution time	Memory
866969		lolismek	Two Antennas (JOI19_antennas)	C++14	0 / 100	172 ms	44908 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, lazy;
    }seg[NMAX + 1];

    Node Merge(Node l, Node r){
        Node ans;
        ans.maxi = max(l.maxi, r.maxi);
        ans.mini = min(l.mini, r.mini);
        ans.diff = max(ans.maxi - ans.mini, max(l.diff, r.diff));
        ans.lazy = +INF;
        return ans;
    }

    void propag(int node, int l, int r){
        seg[node].mini = min(seg[node].mini, seg[node].lazy);
        seg[node].diff = max(seg[node].diff, seg[node].maxi - seg[node].mini);

        if(l < r){
            seg[2 * node].lazy = min(seg[2 * node].lazy, seg[node].lazy);
            seg[2 * node + 1].lazy = min(seg[2 * node + 1].lazy, seg[node].lazy);
        }

        seg[node].lazy = +INF;
    }

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

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

        seg[node] = Merge(seg[2 * node], seg[2 * node + 1]);
    }

    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 = 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].lazy = val;
            propag(node, l, r);
            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] = Merge(seg[2 * node], seg[2 * node + 1]);

        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 querymaxi(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, querymaxi(2 * node, l, mid, ql, qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans, querymaxi(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, i, -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;
}

/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
*/

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