Submission #392808

#	Time	Username	Problem	Language	Result	Execution time	Memory
392808		vaaven	Two Antennas (JOI19_antennas)	C++14	100 / 100	1344 ms	59480 KiB

antennas

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
#define int long  long
  
using namespace std;
  
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
  
const int inf = 1e9 + 228;
const int infll = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;
  
  
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("inputik.txt", "r", stdin);
//    freopen("outputik.txt", "w", stdout);
}
 
const int maxn = 2e5 + 228;
 
int t[maxn*4];
int mx[maxn*4];
int lzupd[maxn*4];
int H[maxn], A[maxn], B[maxn];
int n, q;
int L[maxn], R[maxn];
int ans[maxn];
 
void push(int v, int l, int r){
    if(lzupd[v] != infll){
//        cout << 1 << endl;
//        cout << v << ": " << t[v] << " -> " << t[v] << endl;
        t[v] = max(t[v], mx[v] - lzupd[v]);
        if(l != r){
            lzupd[v*2] = min(lzupd[v*2], lzupd[v]);
            lzupd[v*2+1] = min(lzupd[v*2+1], lzupd[v]);
        }
        lzupd[v] = infll;
    }
}
 
void upd(int v, int l, int r, int k){
    push(v, l, r);
    if(l == r){
        if(mx[v] == -infll){
            mx[v] = H[l];
        } else{
            mx[v] = -infll;
        }
    } else{
        int mid = (l+r)/2;
        if(k <= mid){
            upd(v*2, l, mid, k);
        } else{
            upd(v*2+1, mid+1, r, k);
        }
//        push(v*2, l, mid);
//        push(v*2+1, mid+1, r);
        mx[v] = max(mx[v*2], mx[v*2+1]);
//        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
void sett(int v, int l, int r, int ql, int qr, int k){
    push(v, l, r);
    if(ql <= l && r <= qr){
        lzupd[v] = min(lzupd[v], k);
        push(v, l, r);
    } else if(ql > r || l > qr){
        return;
    } else{
        int mid = (l+r)/2;
        sett(v*2, l, mid, ql, qr, k);
        sett(v*2+1, mid+1, r, ql, qr, k);
        t[v] = max(t[v*2], t[v*2+1]);
//        mx[v] = max(mx[v*2], mx[v*2+1]);
    }
}
 
int get(int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if(ql <= l && r <= qr){
        return t[v];
    } else if(l > qr || ql > r){
        return -1;
    } else{
        int mid = (l+r)/2;
        return max(get(v*2, l, mid, ql, qr), get(v*2+1, mid+1, r, ql, qr));
    }
//    cout << t[1] << endl;
}
 
void solve2(){
    vvi to_add(n+1);
    vvi to_del(n+1);
    vvi posts(n+1);
    for(int &i:lzupd)
        i = infll;
    for(int &i:t)
        i = -infll;
    for(int &i:mx)
        i = -infll;
    for(int i=0; i<q; i++){
        posts[R[i]].pb(i);
    }
    for(int i=0; i<n; i++){
        if(i + A[i] < n){
            to_add[i + A[i]].pb(i);
            to_del[min(i + B[i] + 1, n)].pb(i);
        }
        for(int j:to_add[i])
            upd(1, 0, maxn, j);
        for(int j:to_del[i])
            upd(1, 0, maxn, j);
        if(i - A[i] >= 0){
            sett(1, 0, maxn, max(i - B[i], 0ll), i - A[i], H[i]);
        }
        for(int j:posts[i]){
//            cout << L[j] << " " << R[j] << " " << get(1, 0, maxn, L[j], R[j]) << endl;
            ans[j] = max(ans[j], get(1, 0, maxn, L[j], R[j]));
        }
    }
}
 
void solve(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> H[i] >> A[i] >> B[i];
    }
    for(int &i:ans)
        i = -1;
//    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
    }
    solve2();
    for(int &i:H)
        i = -i;
    solve2();
    for(int i=0; i<q; i++)
        cout << ans[i] << endl;
}
/*
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
=======
 20
 260055884 2 15
 737689751 5 5
 575359903 1 15
 341907415 14 14
 162026576 9 19
 55126745 10 19
 95712405 11 14
 416027186 8 13
 370819848 11 14
 629309664 4 13
 822713895 5 15
 390716905 13 17
 577166133 8 19
 195931195 10 17
 377030463 14 17
 968486685 11 19
 963040581 4 10
 566835557 1 12
 586336111 6 16
 385865831 8 9
 1
 1 20
 */
signed main(){
     fast_io();
//  ;(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

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