Submission #1274768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274768		hainam2k9	Two Antennas (JOI19_antennas)	C++20	100 / 100	277 ms	34020 KiB

antennas

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
struct SegmentTree{
    struct Node{
        int MIN=1e9,MAX=-1e9,val=-1;
    }sgt[MAXN<<2],lazy[MAXN<<2];
    void down(int id){
        sgt[id<<1].val=max({sgt[id<<1].val,sgt[id<<1].MAX-lazy[id].MIN,lazy[id].MAX-sgt[id<<1].MIN});
        sgt[id<<1|1].val=max({sgt[id<<1|1].val,sgt[id<<1|1].MAX-lazy[id].MIN,lazy[id].MAX-sgt[id<<1|1].MIN});
        lazy[id<<1].MAX=max(lazy[id<<1].MAX,lazy[id].MAX), lazy[id<<1].MIN=min(lazy[id<<1].MIN,lazy[id].MIN);
        lazy[id<<1|1].MAX=max(lazy[id<<1|1].MAX,lazy[id].MAX), lazy[id<<1|1].MIN=min(lazy[id<<1|1].MIN,lazy[id].MIN);
        lazy[id].MAX=-1e9, lazy[id].MIN=1e9;
    }
    void update(int id, int l, int r, int pos, int val, bool add){
        if(pos<l||r<pos) return;
        if(l==r){
            if(add) sgt[id].MIN=sgt[id].MAX=val;
            else sgt[id].MIN=1e9, sgt[id].MAX=-1e9;
            return;
        }
        down(id);
        int mid=(l+r)>>1;
        update(id<<1,l,mid,pos,val,add);
        update(id<<1|1,mid+1,r,pos,val,add);
        sgt[id].val=max(sgt[id<<1].val,sgt[id<<1|1].val);
        sgt[id].MIN=min(sgt[id<<1].MIN,sgt[id<<1|1].MIN);
        sgt[id].MAX=max(sgt[id<<1].MAX,sgt[id<<1|1].MAX);
    }
    void update2(int id, int l, int r, int u, int v, int val){
        if(v<l||r<u) return;
        if(u<=l&&r<=v){
            sgt[id].val=max({sgt[id].val,val-sgt[id].MIN,sgt[id].MAX-val});
            lazy[id].MAX=max(lazy[id].MAX,val), lazy[id].MIN=min(lazy[id].MIN,val);
            return;
        }
        down(id);
        int mid=(l+r)>>1;
        update2(id<<1,l,mid,u,v,val);
        update2(id<<1|1,mid+1,r,u,v,val);
        sgt[id].val=max(sgt[id<<1].val,sgt[id<<1|1].val);
    }
    int getmax(int id, int l, int r, int u, int v){
        if(v<l||r<u) return -1;
        if(u<=l&&r<=v) return sgt[id].val;
        down(id);
        int mid=(l+r)>>1;
        return max(getmax(id<<1,l,mid,u,v),getmax(id<<1|1,mid+1,r,u,v));
    }
}ST;
int n,q,a[MAXN],rs[MAXN];
pair<int,int> p[MAXN];
vector<pair<int,int>> query[MAXN],v[MAXN];
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n;
    for(int i = 1; i<=n; ++i){
        cin >> a[i] >> p[i].fi >> p[i].se;
        if(i+p[i].fi<=n) v[i+p[i].fi].pb(i,1);
        if(i+p[i].se+1<=n) v[i+p[i].se+1].pb(i,0);
    }
    cin >> q;
    for(int i = 1; i<=q; ++i){
        int l,r;
        cin >> l >> r;
        query[r].pb(l,i);
    }
    for(int i = 1; i<=n; ++i){
        for(pair<int,int>& p : v[i])
            ST.update(1,1,n,p.fi,a[p.fi],p.se);
        if(i-p[i].fi>=1) ST.update2(1,1,n,max(1,i-p[i].se),i-p[i].fi,a[i]);
        for(pair<int,int>& p : query[i])
            rs[p.se]=ST.getmax(1,1,n,p.fi,i);
    }
    for(int i = 1; i<=q; ++i)
        cout << rs[i] << "\n";
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:75:45: note: in expansion of macro 'fo'
   75 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
antennas.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:75:45: note: in expansion of macro 'fo'
   75 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

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