Submission #1093482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093482		vjudge1	Two Antennas (JOI19_antennas)	C++17	2 / 100	3093 ms	55432 KiB

antennas

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N  = 2e5 + 2;
const int block = 355 + 2;
const ll inf = 1e18 + 2;
int n , q;
vector < int  > df[N + 2];
vector < int > aa[N + 2];
struct kt {
    int l , r , id;
    bool operator<(const kt &t)const{
        return r < t.r;
    }
};
ll mx[4 * N + 2];
ll mn[4 * N + 2];
void update_mx(int id , int l , int r , int p , ll val){
    if(l > p || r < p)return;
    if(l == r){
        mx[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    update_mx(id * 2 , l , mid , p , val);
    update_mx(id * 2 + 1 , mid + 1 , r , p , val);
    mx[id] = max(mx[id * 2] , mx[id * 2 + 1]);
}
void update_mn(int id , int l , int r , int p , ll val){
    if(l > p || r < p)return;
    if(l == r){
        mn[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    update_mn(id * 2 , l , mid , p , val);
    update_mn(id * 2 + 1 , mid + 1 , r , p , val);
    mn[id] = min(mn[id * 2] , mn[id * 2 + 1]);
}
ll get_mx(int id , int l , int r , int u , int v){
    if(l > v|| r <u) return -inf;
    if(u <= l && r <= v)return mx[id];
    int mid = (l + r) / 2;
    return max(get_mx(id * 2 , l , mid , u , v) , get_mx(id * 2 + 1 , mid + 1 , r , u , v));
}
ll get_mn(int id , int l , int r , int u , int v){
    if(l > v|| r <u) return inf;
    if(u <= l && r <= v)return mn[id];
    int mid = (l + r) / 2;
    return min(get_mn(id * 2 , l , mid , u , v) , get_mn(id * 2 + 1 , mid + 1 , r , u , v));
}
vector < kt > query[N / block + 2];
ll ans[N + 2];
ll h[N + 2];
int  lx[N + 2] , rx[N + 2];
void cal(int num_block){
    sort(query[num_block].begin(),  query[num_block].end());
    int l = (num_block + 1) * block;
    int lim = (num_block + 1) * block - 1;
    for(int i = 1; i <= n ; i ++){
        df[i].clear();
        aa[i].clear();
        update_mn(1 , 1 , n , i , inf);
        update_mx(1 , 1 , n , i , -inf);
    }
    ll val = -1;
    for(auto cur : query[num_block]){
        while(l <= cur.r){
            for(auto v: df[l]){
                update_mn(1 ,1 , n , v , h[v]);
                update_mx(1 ,1 , n ,v , h[v]);
            }
            val = max(val , get_mx(1 , 1 , n , max(0 , l - rx[l]) , max(0 , l - lx[l])) - h[l]);
            val = max(val , h[l] - get_mn(1 , 1 , n , max(0 , l - rx[l]) , max(0 , l - lx[l])));
            for(auto v: aa[l]){
                update_mn(1 ,1 , n, v , inf);
                update_mx(1 , 1 , n , v , -inf);
            }
            df[min(n + 1 , l + lx[l])].push_back(l);
            aa[min(n + 1 , l + rx[l])].push_back(l);
            df[max(0 , l - lx[l])].push_back(l);
            aa[max(0 , l  - rx[l])].push_back(l);
            l ++;
        }
        ans[cur.id] = val;
        for(int i = lim ; i >= cur.l; i --){
            for(auto v: df[i]){
                update_mn(1 ,1 , n , v , h[v]);
                update_mx(1 ,1 , n ,v , h[v]);
            }
            ans[cur.id] = max(ans[cur.id] , get_mx(1 , 1 , n , min(n + 1 , i + lx[i]) , min(n + 1 , i + rx[i])) - h[i]);
            ans[cur.id] = max(ans[cur.id] , h[i] - get_mn(1 , 1 , n , min(n + 1 , i + lx[i]) , min(n + 1 , i + rx[i])));
            for(auto v: aa[l]){
                update_mn(1 ,1 , n, v , inf);
                update_mx(1 , 1 , n , v , -inf);
            }
            df[max(0 , i - lx[i])].push_back(i);
            aa[max(0 , i  - rx[i])].push_back(i);
        }
        for(int i = cur.l;i <= lim;i ++){
            df[max(0 , i - lx[i])].pop_back();
            aa[max(0 , i  - rx[i])].pop_back();
        }
    }
}
void cc(int l , int r , int id){
    ans[id] = -1;
    for(int i = l ; i <= r ; i ++){
        df[i].clear();
        aa[i].clear();
    }
    for(int i = r ; i >= l; i--){
        for(auto v: df[i]){
            update_mn(1 , 1 , n , v , h[v]);
            update_mx(1 , 1 , n , v, h[v]);
           
        } 
        ans[id] = max(ans[id] , get_mx(1 , 1 , n , min(n + 1 , i + lx[i]) , min(n + 1 , i + rx[i])) - h[i]);
        ans[id] = max(ans[id] , h[i] - get_mn(1 , 1 , n , min(n + 1 , i + lx[i]) , min(n + 1 , i + rx[i])));
        if(i == 1){
     //       cout <<  get_mn(1 , 1 , n , min(n + 1 , i + lx[i]) , min(n + 1 , i + rx[i])) << '\n';
        }
        for(auto v: aa[i]){
            update_mn(1 ,1 , n, v , inf);
            update_mx(1 , 1 , n , v , -inf);
        }
        df[max(0 , i - lx[i])].push_back(i);
        aa[max(0 , i  - rx[i])].push_back(i);
     //   if(i == 3) cout << max(0 , i - lx[i]) << ' ' << max(0 , i  - rx[i]) << '\n';

    }
     for(int i = l ; i <= r; i ++){
        update_mn(1 , 1 , n , i , inf);
        update_mx(1 , 1 , n , i , -inf);
    }
}
void solve() {
    memset(mn , 0x3f , sizeof(mn));
    memset(mx , -0x3f , sizeof(mx));
    cin >> n;
    for(int i = 1; i <= n ; i ++){
        cin >> h[i] >> lx[i] >> rx[i];
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q ;i ++){
        int l , r;
        cin >> l >> r;
        if(l / block == r / block){
           cc(l , r , i);
        }
        else{
            query[l / block].push_back({l , r , i});
        }
    }
    for(int i = 0 ; i <= n / block; i ++){
        cal(i);
    }
    for(int i  = 1; i <= q ;i  ++){
        cout << ans[i] << '\n';
    }

    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    #define _ "joi2."
    if (fopen(_ "inp", "r")) {
        freopen(_ "inp", "r", stdin);
        freopen(_ "out", "w", stdout);
    }
    
    solve();
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(_ "inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
antennas.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(_ "out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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