Submission #999590

#	Time	Username	Problem	Language	Result	Execution time	Memory
999590		MarwenElarbi	Two Antennas (JOI19_antennas)	C++17	22 / 100	262 ms	19640 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct q{
  int x,type,idx;
  bool operator<(const q &o) const{
    if(x!=o.x) return x<o.x;
    else return type<o.type;
  }
};
int h[nax],a[nax],b[nax];
int segtree[nax*4][2];
void build(int pos,int l,int r){
  if(l==r){
    segtree[pos][0]=1e9;
    segtree[pos][1]=-1e9;
    return;
  }
  int mid=(r+l)/2;
  build(pos*2+1,l,mid);
  build(pos*2+2,mid+1,r);
  segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
  segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
  return;
}
void update(int pos,int l,int r,int idx,int value){
  if(l==r){
    if(value==1) segtree[pos][0]=segtree[pos][1]=h[l];
    else{
      segtree[pos][0]=1e9;
      segtree[pos][1]=-1e9;
    }
    return;
  }
  int mid=(r+l)/2;
  if(idx<=mid) update(pos*2+1,l,mid,idx,value);
  else update(pos*2+2,mid+1,r,idx,value);
  segtree[pos][0]=min(segtree[pos*2+1][0],segtree[pos*2+2][0]);
  segtree[pos][1]=max(segtree[pos*2+1][1],segtree[pos*2+2][1]);
  return;
}
int query1(int pos,int l,int r,int left,int right){
  if(l>r||l>right||r<left) return 1e9;
  else if(l>=left&&r<=right) return segtree[pos][0];
  int mid=(r+l)/2;
  return min(query1(pos*2+1,l,mid,left,right),query1(pos*2+2,mid+1,r,left,right));
}
int query2(int pos,int l,int r,int left,int right){
  if(l>r||l>right||r<left) return -1e9;
  else if(l>=left&&r<=right) return segtree[pos][1];
  int mid=(r+l)/2;
  return max(query2(pos*2+1,l,mid,left,right),query2(pos*2+2,mid+1,r,left,right));
}
int main() {
  int n;
  cin>>n;
  vector<q> sweep;
  for (int i = 0; i < n; ++i)
  {
    cin>>h[i]>>a[i]>>b[i];
    sweep.pb({i,1,i});
    if(a[i]>i) continue;
    sweep.pb({i-a[i],2,i});
    sweep.pb({max(i-b[i],0),0,i});
  }
  sort(sweep.begin(),sweep.end());
  int ans=0;
  build(0,0,n-1);
  for (int i = 0; i < sweep.size(); ++i)
  {
    //cout <<sweep[i].x<<" "<<sweep[i].type<<" "<<sweep[i].idx<<endl;
    auto cur=sweep[i];
    if(cur.type==0){
      update(0,0,n-1,cur.idx,1);
    }else if(cur.type==1){
      if(cur.idx+a[cur.idx]>n-1) continue;
      int x=h[cur.idx]-query1(0,0,n-1,cur.idx+a[cur.idx],cur.idx+b[cur.idx]);
      int y=query2(0,0,n-1,cur.idx+a[cur.idx],cur.idx+b[cur.idx])-h[cur.idx];
      //cout <<cur.idx<<" "<<x<<" "<<y<<endl;
      ans=max(ans,max(x,y));
    }else update(0,0,n-1,cur.idx,0);
  }
  cout <<ans<<endl;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<q>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < sweep.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~

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