Submission #1053604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053604		Gray	Radio Towers (IOI22_towers)	C++17	23 / 100	4059 ms	5084 KiB

towers

#include "towers.h"
#include <algorithm>
#include <vector>

#define ll int
#define ff first
#define ss second
#define ln "\n"

using namespace std;


struct Fenwick{
     vector<ll> tr;
     ll n;
     Fenwick(ll N){
          n=N;
          tr.resize(N+1);
     }
     void update(ll i, ll x){
          for (; i<=n; i+=(-i&i)){
               tr[i]=max(tr[i], x);
          }
     }
     ll query(ll i){
          ll ans=0;
          for (; i; i-=(-i&i)) ans=max(ans, tr[i]);
          return ans;
     }
};

struct Fenwick2{
     vector<ll> tr;
     ll n;
     Fenwick2(ll N){
          n=N;
          tr.resize(N+1);
     }
     void update(ll i, ll x){
          for (; i; i-=(-i&i)){
               tr[i]=max(tr[i], x);
          }
     }
     ll query(ll i){
          ll ans=0;
          for (; i<=n; i+=(-i&i)) ans=max(ans, tr[i]);
          return ans;
     }
};
vector<int> a, sa;
ll getind(ll x){
     return lower_bound(sa.begin(), sa.end(), x)-sa.begin();
}
ll n;
void init(int N, std::vector<int> H) {
     a=H;
     n=N;
}
// smallt -> 
// bigt -> 
int max_towers(int L, int R, int D) {
     sa.clear();
     sa=a;
     for (auto ch:a){
          sa.push_back(ch+D);
          sa.push_back(max(0, ch-D));
     }
     sort(sa.begin(), sa.end());
     sa.erase(unique(sa.begin(), sa.end()), sa.end());

     Fenwick bigt(sa.size());
     Fenwick2 smallt(sa.size());
     ll mx=0;
     for (ll i=L; i<=R; i++){
          ll cur = smallt.query(getind(a[i]+D))+1;
          mx=max(mx, cur);
          if (a[i]>=D) smallt.update(getind(a[i]), bigt.query(getind(a[i]-D)));
          bigt.update(getind(a[i]), cur);
     }
     return mx;
}

• 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