Submission #1040994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040994		_8_8_	Radio Towers (IOI22_towers)	C++17	21 / 100	787 ms	335860 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
int n,pos;
vector<int> h;
const int N = 2e5 + 12,B = 20;
int sp[20][N],p[20][N],lg[N],sp1[20][N],p1[20][N];
bool sub = false;
void build() {
    for(int i = 0;i < n;i++){
        sp1[0][i] = sp[0][i] = h[i];
        p1[0][i] = p[0][i] = i;
    }
    for(int i = 1;i < B;i++) {
        for(int j = 0;j + (1 << i) - 1 < n;j++) {
            int X = sp[i - 1][j],Y = sp[i - 1][j + (1 << (i - 1))];
            sp[i][j] = min(X,Y);
            if(sp[i][j] == X) {
                p[i][j] = p[i - 1][j];
            }else {
                p[i][j] = p[i - 1][j + (1 << (i - 1))];
            }
            X = sp1[i - 1][j],Y = sp1[i - 1][j + (1 << (i - 1))];
            sp1[i][j] = max(X,Y);
            if(sp1[i][j] == X) {
                p1[i][j] = p1[i - 1][j];
            }else {
                p1[i][j] = p1[i - 1][j + (1 << (i - 1))];
            }
        }
    }
}
pair<int,int> get(int L,int R) {
    int i = lg[R - L + 1];
    pair<int,int> x = make_pair(sp[i][L],p[i][L]);
    pair<int,int> y = make_pair(sp[i][R - (1 << i) + 1],p[i][R - (1 << i) + 1]);
    return min(x,y);
}
pair<int,int> get1(int L,int R) {
    int i = lg[R - L + 1];
    pair<int,int> x = make_pair(sp1[i][L],p1[i][L]);
    pair<int,int> y = make_pair(sp1[i][R - (1 << i) + 1],p1[i][R - (1 << i) + 1]);
    return max(x,y);
}
int _l[N],_r[N],val[N],_mx[N],_mn[N];
vector<int> b,t;
struct node {
    bool e = true;
    int mx = 0,mn = 1e9,ans = 0,ans1 = 0;
}T[N * 4];
node merge(node l,node r) {
    if(l.e) return r;
    if(r.e) return l;
    node ret;
    ret.e = false;
    ret.mx = max(l.mx,r.mx);
    ret.mn = min(l.mn,r.mn);
    ret.ans = max({l.ans,r.ans,l.mx - r.mn});
    ret.ans1 = max({l.ans1,r.ans1,r.mx - l.mn});
    return ret;
}
void build_(int v = 1,int tl = 0,int tr = n - 1) {
    if(tl == tr) {
        T[v].mx = T[v].mn = h[tl];
        T[v].e = false;
    }else {
        int tm = (tl + tr) >> 1;
        build_(v + v,tl,tm);
        build_(v + v + 1,tm + 1,tr);
        T[v] = merge(T[v + v],T[v + v + 1]);
    }
}
node Get(int l,int r,int v = 1,int tl = 0,int tr = n - 1) {

    if(l > r || tl > r || l > tr) {
        node f;return f;
    }
    if(tl >= l && tr <= r) return T[v];
    int tm = (tl + tr) >> 1;
    return merge(Get(l,r,v+v,tl,tm),Get(l,r,v+v+1,tm+1,tr));
}

struct Node{
    Node *l = 0,*r = 0;
    int mx = 0,mn = (int)1e9,s = 0;
    Node (){}
    Node (int val) {
        mx= mn = val;
        s = 1;
    }
    Node (Node *l_,Node *r_) {
        l = l_;
        r = r_;
        mx = max(l->mx,r->mx);
        mn = min(l->mn,r->mn);
        s = l->s + r->s;
    }
};
using pnode = Node *;
pnode t_[N];
pnode build1(int tl = 0,int tr = n - 1) {
    if(tl == tr) return new Node();
    int tm = (tl + tr) >> 1;
    return new Node(build1(tl,tm),build1(tm + 1,tr));
}
pnode upd(pnode v,int pos,int tl = 0,int tr = n - 1) {
    if(tl == tr) {
        return new Node(tl);
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) {
            return new Node(upd(v->l,pos,tl,tm),v->r);
        } 
        return new Node(v->l,upd(v->r,pos,tm+1,tr));
    }
}
int get_sum(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->s;
    }else {
        int tm = (tl + tr) >> 1;
        return get_sum(l,r,v->l,tl,tm) + get_sum(l,r,v->r,tm+1,tr);
    }
}
int get_mx(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->mx;
    }else {
        int tm = (tl + tr) >> 1;
        return max(get_mx(l,r,v->l,tl,tm),get_mx(l,r,v->r,tm+1,tr));
    }
}
int get_mn(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return (int)1e9;
    if(tl >= l && tr <= r) {
        return v->mn;
    }else {
        int tm = (tl + tr) >> 1;
        return min(get_mn(l,r,v->l,tl,tm),get_mn(l,r,v->r,tm+1,tr));
    }
}
void init(int nn, vector<int> H) {
    n = nn;
    h = H;
    build();
    build_();
    for(int i = 2;i <= n;i++) {
        lg[i] = lg[i / 2] + 1;
    }
    vector<int> st;
    for(int i = 0;i < n;i++) {
        while((int)st.size() && h[st.back()] > h[i]) {
            st.pop_back();
        }
        _l[i] = (st.empty() ? -1 : st.back());
        st.push_back(i);
    }
    st.clear();
    for(int i = n - 1;i >= 0;i--) {
        while(!st.empty() && h[st.back()] > h[i]) {
            st.pop_back();
        }
        _r[i] = (st.empty() ? n : st.back());
        st.push_back(i);
    }
    for(int i = 0;i < n;i++) {
        val[i] = min(get1(_l[i] + 1,i).first,get1(i,_r[i]-1).first) - h[i];
        t.push_back(i);
    }
    sort(t.begin(),t.end(),[&](int x,int y){
        return val[x] < val[y];
    });
    for(int i:t) {
        b.push_back(val[i]);
    }
    _mx[n - 1] = _mn[n - 1] = t.back();
    for(int i = n - 2;i >= 0;i--) {
        _mx[i] = max(t[i],_mx[i + 1]);
        _mn[i] = min(t[i],_mn[i + 1]);
    }
    t_[n] = build1();
    for(int i = n - 1;i >= 0;i--) {
        // cout << i << ' ' << t[i] << ' ' << val[t[i]] << '\n';   
        t_[i] = upd(t_[i + 1],t[i]);
    }
}
bool fq = true;
int up[N * 2][20],up1[N * 2][20];
int F(int x) {
    if(x < n) return x;
    return x - n;
}

bool solver(int x,int y,int d) {
    int l = x,r = y + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get1(x,mid).first >= h[x] + d) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if(r == y + 1) {
        return false;
    }
    x = r;
    node _ = Get(x,y);
    return (_.ans >= d);
}
bool solvel(int x,int y,int d) {
    int l = x - 1,r = y;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get1(mid,y).first >= h[y] + d) {
            l = mid;
        }else {
            r = mid;
        }
    }
    // cout << x << ' ' << y << ' ' << l << '\n';
    if(l == x - 1) return false;
    y = l;
    node _ = Get(x,y);
    return (_.ans1 >= d);
}
int max_towers(int l_, int r_, int d) {
    int it = lower_bound(b.begin(),b.end(),d) - b.begin();
    int ret = 0;
    int l,r;
    if(it == (int)b.size()) {
        l = r = get(l_,r_).second;
        ret++;
    } else {
        l = get_mn(l_,r_,t_[it]);
        r = get_mx(l_,r_,t_[it]);
        ret = get_sum(l_,r_,t_[it]);
    }
    return ret + solvel(l_,l,d) + solver(r,r_,d); 
}

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