Submission #396946

#	Time	Username	Problem	Language	Result	Execution time	Memory
396946		cpp219	Two Antennas (JOI19_antennas)	C++14	0 / 100	2526 ms	41892 KiB

antennas

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e16 + 7;

struct anten{
    ll h,l,r;
};
anten a[N];
ll n,Q,ans[N],l,r;
LL q[N]; /// fs = L   sc = R
vector<LL> v[N]; /// fs = pos   sc = id

ll stC[4*N],stD[4*N],lazy[4*N];

void updC(ll id,ll l,ll r,ll u,ll val){
    if (u < l||r < u) return;
    if (l == r){
        stC[id] = val; return;
    }
    ll mid = (l + r)/2;
    updC(id*2,l,mid,u,val); updC(id*2 + 1,mid + 1,r,u,val);
    stC[id] = max(stC[id*2],stC[id*2 + 1]);
}

ll GetC(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return -inf;
    if (u <= l&&r <= v) return stC[id];
    ll mid = (l + r)/2;
    return max(GetC(id*2,l,mid,u,v),GetC(id*2 + 1,mid + 1,r,u,v));
}

void Pass(ll id,ll l,ll r){
    ll t = lazy[id]; lazy[id] = inf;
    ll mid = (l + r)/2; ll now1 = GetC(1,1,n,l,mid),now2 = GetC(1,1,n,mid + 1,r);
    stD[id*2] = max(stD[id*2],now1 - t); lazy[id*2] = min(lazy[id*2],t);
    stD[id*2 + 1] = max(stD[id*2 + 1],now2 - t); lazy[id*2 + 1] = min(lazy[id*2 + 1],t);
}

void updD(ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        ll now = GetC(1,1,n,l,r);
        stD[id] = max(stD[id],now - val); lazy[id] = min(lazy[id],val);
        return;
    }
    ll mid = (l + r)/2; Pass(id,l,r);
    updD(id*2,l,mid,u,v,val); updD(id*2 + 1,mid + 1,r,u,v,val);
    stD[id] = max(stD[id*2],stD[id*2 + 1]);
}

ll GetD(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return -inf;
    if (u <= l&&r <= v) return stD[id];
    ll mid = (l + r)/2; Pass(id,l,r);
    return max(GetD(id*2,l,mid,u,v),GetD(id*2 + 1,mid + 1,r,u,v));
}

void oper(){
    fill(stC,stC + 4*n + 1,-inf); fill(stD,stD + 4*n + 1,-inf);
    fill(lazy,lazy + 4*n + 1,inf);
    vector<LL> event[N]; /// 1 mean in   -1 mean out
    for (ll i = 1;i <= n;i++){
        ll L = a[i].l,R = a[i].r,H = a[i].h;
        if (i + L <= n) event[i + L].push_back({i,1});
        if (i + R + 1 <= n) event[i + R + 1].push_back({i,-1});
    }
    for (ll i = 1;i <= n;i++){
        ll R = max(1ll,i - a[i].l),L = max(1ll,i - a[i].r),h = a[i].h;
        for (auto j : event[i]){
            if (j.sc < 0) updC(1,1,n,j.fs,-inf);
            else updC(1,1,n,j.fs,a[j.fs].h);
        }
        updD(1,1,n,L,R,h);
        for (auto j : v[i]){
            ll id = j.sc;
            ans[id] = max(GetD(1,1,n,j.fs,i),ans[id]);
        }
    }
}

void Reverse(){
    reverse(a + 1,a + n + 1);
    for (ll i = 1;i <= Q;i++) v[i].clear();
    for (ll i = 1;i <= Q;i++){
        ll L = n + 1 - q[i].sc,R = n + 1 - q[i].fs;
        v[R].push_back({L,i});
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i].h>>a[i].l>>a[i].r;
    cin>>Q; fill(ans,ans + Q + 1,-inf);
    for (ll i = 1;i <= Q;i++){
        cin>>l>>r; q[i] = {l,r};
        v[r].push_back({l,i});
    }
    oper(); Reverse(); oper();
    for (ll i = 1;i <= Q;i++){
        //cout<<ans[i]<<"\n"; continue;
        if (ans[i] < 0) cout<<-1;
        else cout<<ans[i]; cout<<"\n";
    }
}

Compilation message (stderr)

antennas.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
antennas.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
antennas.cpp: In function 'void oper()':
antennas.cpp:73:34: warning: unused variable 'H' [-Wunused-variable]
   73 |         ll L = a[i].l,R = a[i].r,H = a[i].h;
      |                                  ^
antennas.cpp: In function 'int main()':
antennas.cpp:118:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  118 |         else cout<<ans[i]; cout<<"\n";
      |         ^~~~
antennas.cpp:118:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  118 |         else cout<<ans[i]; cout<<"\n";
      |                            ^~~~
antennas.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  104 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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