Submission #1054161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054161		Gray	Radio Towers (IOI22_towers)	C++17	14 / 100	705 ms	24280 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[p2])){
                        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: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23