oj.uz

Submission #999590

# Submission time Handle Problem Language Result Execution time Memory
999590 2024-06-15T20:54:12 Z MarwenElarbi Two Antennas (JOI19_antennas) C++17
22 / 100
 262 ms 19640 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 14256 KB Output is correct
2 Correct 222 ms 13752 KB Output is correct
3 Correct 155 ms 15816 KB Output is correct
4 Correct 218 ms 18184 KB Output is correct
5 Correct 97 ms 10924 KB Output is correct
6 Correct 217 ms 19120 KB Output is correct
7 Correct 190 ms 18868 KB Output is correct
8 Correct 262 ms 19556 KB Output is correct
9 Correct 38 ms 8172 KB Output is correct
10 Correct 219 ms 19612 KB Output is correct
11 Correct 134 ms 12480 KB Output is correct
12 Correct 226 ms 19636 KB Output is correct
13 Correct 193 ms 19124 KB Output is correct
14 Correct 187 ms 19640 KB Output is correct
15 Correct 190 ms 18868 KB Output is correct
16 Correct 224 ms 19280 KB Output is correct
17 Correct 192 ms 19380 KB Output is correct
18 Correct 195 ms 18868 KB Output is correct
19 Correct 224 ms 19120 KB Output is correct
20 Correct 183 ms 18980 KB Output is correct
21 Correct 175 ms 18964 KB Output is correct
22 Correct 214 ms 19128 KB Output is correct
23 Correct 202 ms 18868 KB Output is correct
24 Correct 175 ms 18100 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -