Submission #1054143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054143		Gray	Radio Towers (IOI22_towers)	C++17	0 / 100	499 ms	24016 KiB

towers

#include "towers.h"
#include <algorithm>
#include <vector>
#include <iostream>
#define ll int
#define ff first
#define ss second
#define ln "\n"

using namespace std;
struct SegTree{
     #define node vector<ll>
     vector<node> t;
     ll sz, rsz;
     void init(ll N){
          sz=N*4;
          rsz=N;
          t.resize(sz);
     }
     void clear(){
          t.clear();
          sz=rsz=0;
     }
     void merge(node &p, node &l, node &r){
          ll p1=0, p2=0;
          while (p1<(ll)l.size() or p2<(ll)r.size()){
               if (p2==(ll)r.size() or (p1<(ll)l.size() and l[p1]<r[p1])){
                    p.push_back(l[p1++]);
               }else{
                    p.push_back(r[p2++]);
               }
          }
     }
     void build(ll tl, ll tr, ll v, vector<ll> &a){
          if (tl==tr){
               ll dif=0;
               if (tl-1>=0 and tl+1<(ll)a.size()){
                    dif=max(dif, min(a[tl]-a[tl-1], a[tl]-a[tl+1]));
               }
               t[v].push_back(dif);
          }else{
               ll tm = (tl+tr)/2;
               build(tl, tm, v*2, a);
               build(tm+1, tr, v*2+1, a);
               merge(t[v], t[v*2], t[v*2+1]);
          }
     }
     void build(vector<ll> &a){
          build(0, rsz-1, 1, a);
     }
     void query(ll tl, ll tr, ll v, ll l, ll r, ll D, ll &wr){
          if (tl==l and tr==r){
               wr+=(ll)t[v].size()-(lower_bound(t[v].begin(), t[v].end(), D)-t[v].begin());
          }else if (l>r) return;
          else{
               ll tm = (tl+tr)/2;
               query(tl, tm, v*2, l, min(r, tm), D, wr);
               query(tm+1, tr, v*2+1, max(l, tm+1), r, D, wr);
          }
     }
     ll query(ll l, ll r, ll D){
          ll res=0;
          query(0, rsz-1, 1, l, r, D, res);
          return res;
     }
};

vector<ll> fa;
SegTree tr;
ll fn;
void init(int N, std::vector<int> H) {
     fa=H;
     fn=N;
     tr.clear();
     tr.init(N);
     tr.build(fa);
}
// smallt -> 
// bigt -> 
int max_towers(int L, int R, int D) {
     return tr.query(L+1, R-1, D)+1;
}

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