Submission #1062082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062082		MarwenElarbi	Radio Towers (IOI22_towers)	C++17	23 / 100	4056 ms	4684 KiB

towers

#include <bits/stdc++.h>
using namespace std;
#include "towers.h"
#define pb push_back
#define ll long long
#define fi first
#define se second
const int nax=1e5+5;
int n;
vector<int> tab,cor;
int segtree[nax*4][2];
void update(int pos,int l,int r,int idx,int value,int type){
  if(l==r){
    segtree[pos][type]=value;
    return;
  }
  int mid=(r+l)/2;
  if(idx<=mid) update(pos*2+1,l,mid,idx,value,type);
  else update(pos*2+2,mid+1,r,idx,value,type);
  segtree[pos][type]=max(segtree[pos*2+1][type],segtree[pos*2+2][type]);
}
int query(int pos,int l,int r,int left,int right,int type){
  if(l>r||l>right||r<left) return 0;
  if(l>=left&&r<=right) return segtree[pos][type];
  int mid=(r+l)/2;
  return max(query(pos*2+1,l,mid,left,right,type),query(pos*2+2,mid+1,r,left,right,type));
}
void init(int N, std::vector<int> H) {
  n=N;
  for (int i = 0; i < N; ++i)
  {
    tab.pb(H[i]);
  }
  cor=tab;
  sort(cor.begin(),cor.end());
}

int max_towers(int L, int R, int D){
  int dp[n],dp1[n];
  int ans=0;
  for (int i = L; i <= R; ++i)
  {
    int cur=upper_bound(cor.begin(),cor.end(),tab[i]-D)-cor.begin();
    int pos=lower_bound(cor.begin(),cor.end(),tab[i])-cor.begin();
    cur--;
    dp1[i]=query(0,0,n-1,0,cur,0);
    update(0,0,n-1,pos,dp1[i],1);
    cur=lower_bound(cor.begin(),cor.end(),tab[i]+D)-cor.begin();
    dp[i]=query(0,0,n-1,cur,n-1,1)+1;
    update(0,0,n-1,pos,dp[i],0);
    ans=max(ans,dp[i]);
  }
  return ans;
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23