Submission #895986

#	Time	Username	Problem	Language	Result	Execution time	Memory
895986		1075508020060209tc	Two Antennas (JOI19_antennas)	C++14	22 / 100	423 ms	45016 KiB

antennas

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
struct SGTR{
int l;int r;int mx;
}tr[800005];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].mx=-1;
if(l==r){
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void upd(int nw,int pl,int v){
if(tr[nw].l==pl&&tr[nw].r==pl){
    tr[nw].mx=v;
    return;
}
if(tr[nw].l>pl||tr[nw].r<pl){return;}
upd(nw*2,pl,v);
upd(nw*2+1,pl,v);
tr[nw].mx=max(tr[nw*2].mx,tr[nw*2+1].mx);
}
int qmx(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
    return tr[nw].mx;
}
if(tr[nw].r<l||tr[nw].l>r){
    return -1;
}
return max(qmx(nw*2,l,r),qmx(nw*2+1,l,r));
}
int n;
int hr[200005];
int ar[200005];
int br[200005];
vector<int>event[500005];
int ans;
void solve(){
buildtr(1,1,n);

for(int i=1;i<=n;i++){
    event[i+ar[i]].push_back(i);
    event[i+br[i]+1].push_back(-i);
}

for(int i=1;i<=n;i++){
    for(int j=0;j<event[i].size();j++){
        int id=abs(event[i][j]);
        if(event[i][j]>0){
            upd(1,id,hr[id]);
        }else{
            upd(1,id,-1);
        }
    }
    ans=max(ans,-hr[i]+qmx(1,i-br[i],i-ar[i]));
}


}


signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    cin>>hr[i]>>ar[i]>>br[i];
}
solve();
reverse(ar+1,ar+n+1);
reverse(br+1,br+n+1);
reverse(hr+1,hr+n+1);
for(int i=0;i<=n*2;i++){
    event[i].clear();
}
solve();
cin>>n;
cin>>n;
cin>>n;
cout<<ans<<"\n";


}

Compilation message (stderr)

antennas.cpp: In function 'void solve()':
antennas.cpp:54:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int j=0;j<event[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~~

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