Submission #1280069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280069		ZeroCool	Two Antennas (JOI19_antennas)	C++20	22 / 100	255 ms	38428 KiB

antennas

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


#define ll long long
#define ar array
#define ld double
#define int long long
#define all(v) v.begin(), v.end()
 #pragma GCC optimize("O3,Ofast,unroll-loops")

const int N = 5e5 + 20;
const int K = 467;
const int M = 20;
const int LOG = 20;
const int INF = 1e15;	
int MOD = 1e9 + 7;
const ld EPS = 1e-12;

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

struct Node{
    int lz;
    int ans;
    int mx;

    Node(){
        ans = -1, mx = -INF, lz = INF;
    }
    Node(int a,int b,int c){
        ans = a, mx = b, lz = c;
    }
};

Node operator+(Node a, Node b){
    Node ret;
    ret.ans = max(a.ans, b.ans);
    ret.mx = max(a.mx, b.mx);
    ret.lz = INF;
    return ret;
}

struct SGT{
    vector<Node> s;

    SGT(int n){
        s.resize(4 * n);
    }
    void psh(int k,int tl,int tr){
        chmax(s[k].ans, s[k].mx -s[k].lz);
        if(tl != tr){
            chmin(s[k * 2].lz, s[k].lz);
            chmin(s[k * 2 + 1].lz, s[k].lz);
        }
        s[k].lz = INF;
    }

    void upd1(int k,int tl,int tr,int p,int v){
        psh(k, tl, tr);
        if(tl == tr){
            s[k].mx = v;
            // psh(k, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        if(p <= tm)upd1(k * 2, tl, tm, p, v);
        else upd1(k * 2 + 1, tm + 1, tr, p, v);
        psh(k * 2, tl, tm);
        psh(k * 2 + 1, tm + 1, tr);
        s[k] = s[k * 2] + s[k * 2 + 1];
    }

    void upd2(int k,int tl,int tr,int l,int r,int v){
        psh(k, tl, tr);
        if(l > tr || tl > r || l > r)return;
        if(l <= tl && tr <= r){
            s[k].lz = v;
            psh(k, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        upd2(k * 2, tl, tm, l, r, v);
        upd2(k * 2 + 1, tm + 1, tr, l, r, v);
        // psh(k * 2, tl, tm);
        // psh(k * 2 + 1, tm + 1, tr);
        s[k] = s[k * 2] + s[k * 2 + 1];
    }

    int qry(int k,int tl,int tr,int l,int r){
        if(l > tr || tl > r || l > r)return -1;
        if(l <= tl && tr <= r)return s[k].ans;
        int tm = (tl + tr) / 2;
        return max(qry(k * 2, tl, tm, l, r), qry(k * 2 + 1, tm + 1, tr, l, r));
    }
};

void orz(){
    int n;
    cin>>n;
    int A[n], L[n], R[n];
    for(int i =0 ;i < n;i++)cin>>A[i]>>L[i]>>R[i];
    int q;
    cin>>q;
    ar<int,2> Q[q];
    for(int i = 0;i < q;i++){
        int l, r;
        cin>>l>>r;
        --l, --r;
        Q[i] = {l, r};
    } 
    int ans[q];
    memset(ans, -1, sizeof ans);
    for(int it = 0;it < 2;it++){
        vector<ar<int,2>> ev[n];

        for(int i = 0;i < n;i++){
            int l = i + L[i];
            int r = i + R[i];
            if(l < n)ev[l].push_back({i, 1});
            if(r + 1 < n)ev[r + 1].push_back({i, -1});
        }
        vector<int> que[n];
        for(int i = 0;i < q;i++)que[Q[i][1]].push_back(i);
        
       SGT sgt(n);

        for(int i = 0;i < n;i++){
            for(auto [j, b]: ev[i]){
                if(b > 0)sgt.upd1(1, 0, n - 1, j, A[j]);
               else sgt.upd1(1, 0, n - 1, j, -INF);
            }
           sgt.upd2(1, 0, n - 1, max(0ll, i - R[i]), i - L[i], A[i]);
            for(auto j: que[i]){
                auto [l, r] = Q[j];
               chmax(ans[j], sgt.qry(1, 0, n - 1,l, r));
            }
            
        }


        reverse(A, A + n);
        reverse(L, L + n);
        reverse(R, R + n);
        for(int i = 0;i < q;i++){
            Q[i][0] = n - Q[i][0] - 1;
            Q[i][1] = n - Q[i][1] - 1;
            swap(Q[i][0], Q[i][1]);
        }
    }
    for(int i = 0;i < q;i++)cout<<ans[i]<<'\n';
    cout<<'\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //  cin>>t;
    while (t--)orz();
}  

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