Submission #207665

#	Time	Username	Problem	Language	Result	Execution time	Memory
207665		Mercenary	Two Antennas (JOI19_antennas)	C++14	100 / 100	818 ms	47736 KiB

antennas

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

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
const int inf = 1e9 + 1;

struct segTree{
    int mx[maxn * 4],lz[maxn * 4],ans[maxn * 4];
    void reset(){
        fill_n(mx,maxn*4,0);
        fill_n(lz,maxn*4,inf);
        fill_n(ans,maxn*4,-1);
    }
    void push(int x , bool key){
        ans[x] = max(ans[x],mx[x]-lz[x]);
        if(key)lz[x*2] = min(lz[x*2],lz[x]),lz[x*2+1] = min(lz[x * 2 + 1],lz[x]);
        lz[x] = inf;
    }
    void updateP(int x , int l , int r , int pos , int val){
        push(x,l != r);
        if(l == r){
            mx[x] = val;
            return;
        }
        int mid = l + r >> 1;
        if(pos <= mid)updateP(x*2,l,mid,pos,val);
        else updateP(x*2+1,mid+1,r,pos,val);
        ans[x] = max({ans[x],ans[x * 2],ans[x * 2 + 1]});
        mx[x] = max(mx[x * 2] , mx[x * 2 + 1]);
    }
    void updateR(int x , int l , int r , int L , int R , int val){
        push(x,l!=r);
        if(l > R || L > r)return;
        if(L <= l && r <= R){
            lz[x] = min(lz[x],val);push(x,l!=r);return;
        }
        int mid = l + r >> 1;
        updateR(x*2,l,mid,L,R,val);
        updateR(x*2+1,mid+1,r,L,R,val);
        ans[x] = max({ans[x],ans[x * 2],ans[x * 2 + 1]});
        mx[x] = max(mx[x * 2],mx[x * 2 + 1]);
    }
    int query(int x , int l , int r , int L , int R){
        push(x,l!=r);
        if(l > R || L > r)return -1;
        if(L <= l && r <= R)return ans[x];
        int mid = l + r >> 1;
        return max(query(x*2,l,mid,L,R),query(x*2+1,mid+1,r,L,R));
    }
}s;
int n , q;
int a[maxn],b[maxn],h[maxn];
ii queries[maxn];
int ans[maxn];
vector<ii> Q[maxn];
vector<int> avai[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> h[i] >> a[i] >> b[i];
    }
    cin >> q;
    for(int i = 1 ; i <= q ; ++i){
        cin >> queries[i].first >> queries[i].second;
        ans[i] = -1;
    }
    {
        //h[i] - h[j]
        for(int i = 1 ; i <= q ; ++i){
            Q[queries[i].second].pb(mp(queries[i].first,i));
        }
        s.reset();
        for(int i = 1 ; i <= n ; ++i){
            if(i + a[i] <= n){
                avai[i + a[i]].pb(i);
            }
            if(i + b[i] + 1 <= n){
                avai[i + b[i] + 1].pb(-i);
            }
            for(auto c : avai[i]){
                if(c > 0)s.updateP(1,1,n,c,h[c]);
                else s.updateP(1,1,n,-c,0);
            }
            avai[i].clear();
            s.updateR(1,1,n,i-b[i],i-a[i],h[i]);
            for(auto c : Q[i]){
                ans[c.second] = max(ans[c.second],s.query(1,1,n,c.first,i));
            }
            Q[i].clear();
        }
    }
    {
        //-h[i] + h[j]
        for(int i = 1 ; i <= q ; ++i){
            Q[queries[i].first].pb(mp(queries[i].second,i));
        }
        s.reset();
        for(int i = n ; i >= 1 ; --i){
            if(i - a[i] >= 1){
                avai[i - a[i]].pb(i);
            }
            if(i - b[i] - 1 >= 1){
                avai[i - b[i] - 1].pb(-i);
            }
            for(auto c : avai[i]){
                if(c > 0)s.updateP(1,1,n,c,h[c]);
                else s.updateP(1,1,n,-c,0);
            }
            avai[i].clear();
            s.updateR(1,1,n,i+a[i],i + b[i],h[i]);
            for(auto c : Q[i]){
                ans[c.second] = max(ans[c.second],s.query(1,1,n,i,c.first));
            }
            Q[i].clear();
        }
    }
    for(int i = 1 ; i <= q ; ++i)cout << ans[i] << '\n';
}

Compilation message (stderr)

antennas.cpp: In member function 'void segTree::updateP(int, int, int, int, int)':
antennas.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
antennas.cpp: In member function 'void segTree::updateR(int, int, int, int, int, int)':
antennas.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
antennas.cpp: In member function 'int segTree::query(int, int, int, int, int)':
antennas.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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