Submission #216041

#	Time	Username	Problem	Language	Result	Execution time	Memory
216041		Alexa2001	Two Antennas (JOI19_antennas)	C++17	100 / 100	823 ms	67704 KiB

antennas

#include <bits/stdc++.h>
#define yes { cout << "YES" << endl; exit(0); }
#define no { cout << "NO" << endl; exit(0); }
#define impossible { cout << "Impossible" << endl; exit(0); }

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;

const int inf = 1e9;
const int Nmax = 4e5 + 5;

int L[Nmax], R[Nmax], ans[Nmax], H[Nmax], A[Nmax], B[Nmax];
int n, q;

vector<int> when[Nmax], add[Nmax], er[Nmax];


#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


class SegTree
{
    int val[Nmax<<2], best[Nmax<<2], lazy[Nmax<<2];

    void propag(int node)
    {
        if(lazy[node] == inf) return;
        
        lazy[left_son] = min(lazy[left_son], lazy[node]);
        best[left_son] = max(best[left_son], val[left_son] - lazy[left_son]);

        lazy[right_son] = min(lazy[right_son], lazy[node]);
        best[right_son] = max(best[right_son], val[right_son] - lazy[right_son]);
        
        lazy[node] = inf;
    }

public:
    void init(int node, int st, int dr)
    {
        best[node] = -inf;
        val[node] = -inf;
        lazy[node] = inf;
        
        if(st == dr) return;

        init(left_son, st, mid);
        init(right_son, mid+1, dr);
    }

    void upd1(int node, int st, int dr, int pos, int mxVal)
    {
        if(st == dr)
        {
            val[node] = mxVal;
       //     best[node] = max(best[node], val[node] - lazy[node]);
            lazy[node] = inf;
            return;
        }

        propag(node);

        if(pos <= mid) upd1(left_son, st, mid, pos, mxVal);
            else upd1(right_son, mid+1, dr, pos, mxVal);

        val[node] = max(val[left_son], val[right_son]);
        best[node] = max(best[left_son], best[right_son]);
    }

    void upd2(int node, int st, int dr, int L, int R, int mnVal)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] = min(lazy[node], mnVal);
            best[node] = max(best[node], val[node] - lazy[node]);
            return;
        }

        propag(node);

        if(L <= mid) upd2(left_son, st, mid, L, R, mnVal);
        if(mid < R) upd2(right_son, mid+1, dr, L, R, mnVal);

    //    val[node] = max(val[left_son], val[right_son]);
        best[node] = max(best[left_son], best[right_son]);
    }

    int query(int node, int st, int dr, int L, int R)
    {
        if(L > dr || R < st) return -inf;
        if(L <= st && dr <= R) return best[node];

        propag(node);
        return max( query(left_son, st, mid, L, R), query(right_son, mid+1, dr, L, R) );
    }
} aint;


void solve()
{
    aint.init(1, 1, n);

    int i;
    for(i=1; i<=n; ++i) 
    {
        add[i+A[i]].push_back(i);
        er[i+B[i]].push_back(i);
    }

    for(i=1; i<=q; ++i)
        when[R[i]].push_back(i);

    for(i=1; i<=n; ++i)
    {
        for(auto it : add[i])
            aint.upd1(1, 1, n, it, H[it]);
        
        int l, r;
        l = max(1, i - B[i]);
        r = i - A[i];
        
        if(l <= r)
           aint.upd2(1, 1, n, l, r, H[i]);

        for(auto it : when[i])
            ans[it] = max(ans[it], aint.query(1, 1, n, L[it], i));

        for(auto it : er[i])
            aint.upd1(1, 1, n, it, -inf);
    }
}

void clr()
{
    int i;
    for(i=1; i<=n; ++i)
    {
        when[i].clear();
        add[i].clear();
        er[i].clear();
    }
}

int main()
{
    cin.sync_with_stdio(false); cin.tie(0);
    
    int i;
    cin >> n;
    for(i=1; i<=n; ++i) cin >> H[i] >> A[i] >> B[i];
    
    cin >> q;
    for(i=1; i<=q; ++i)
    {
        ans[i] = -1;
        cin >> L[i] >> R[i];
    }    

    solve();
    clr();

    for(i=1; i<=q; ++i) 
    {
        L[i] = n+1-L[i];
        R[i] = n+1-R[i];
        swap(L[i], R[i]);
    }

    reverse(H+1, H+n+1);
    reverse(A+1, A+n+1);
    reverse(B+1, B+n+1);

    solve();

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

    return 0;
}

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