Submission #626675

#	Time	Username	Problem	Language	Result	Execution time	Memory
626675		tlwpdus	Radio Towers (IOI22_towers)	C++17	44 / 100	4043 ms	811168 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int INF = 0x3f3f3f3f;

struct PersSeg {
    vector<int> tree;
    vector<int> le;
    vector<int> ri;
    vector<int> roots;
    int n;
    int _init(int s, int e) {
        if (s==e) {
            int p =tree.size();
            tree.push_back(0);
            le.push_back(-1);
            ri.push_back(-1);
            return p;
        }
        int m = (s+e)/2;
        int l = _init(s,m);
        int r = _init(m+1,e);
        int p =tree.size();
        tree.push_back(0);
        le.push_back(l);
        ri.push_back(r);
        return p;
    }
    void init(int _n) {
        n = _n;
        if (n==0) return;
        roots.push_back(_init(0,n-1));
    }
    int upd(int idx, int val, int s, int e, int ori) {
        if (idx<s||e<idx) {
            return ori;
        }
        if (s==e) {
            int p = tree.size();
            tree.push_back(tree[ori]+val);
            le.push_back(-1);
            ri.push_back(-1);
            return p;
        }
        int m =(s+e)/2;
        int l = upd(idx,val,s,m,le[ori]);
        int r = upd(idx,val,m+1,e,ri[ori]);
        int p = tree.size();
        tree.push_back(tree[ori]+val);
        le.push_back(l);
        ri.push_back(r);
        return p;
    }
    void upd(int idx, int val) {
        if (n==0) return;
        int root = upd(idx, val, 0, n-1, roots.back());
        roots.push_back(root);
    }
    int getv(int S, int E, int s, int e, int ori) {
        if (e<S||E<s) return 0;
        if (S<=s&&e<=E) return tree[ori];
        int m = (s+e)/2;
        return getv(S,E,s,m,le[ori])+getv(S,E,m+1,e,ri[ori]);
    }
    int getv(int S, int E, int ori) {
        return getv(S,E,0,n-1,ori);
    }
};

struct Seg {
    vector<pii> tree[270000]; // v, r
    vector<int> comp[270000]; // r
    vector<int> rootnum[270000];
    PersSeg per[270000];
    const int key = 131072;
    void upd(int idx, pii p) {
        idx += key;
        while(idx) {
            tree[idx].push_back(p);
            idx/=2;
        }
    }
    void calc() {
        for (int i=1;i<key*2;i++) {
//            printf("%d!\n",i);
            sort(tree[i].begin(),tree[i].end());
            for (pii &p : tree[i]) {
                comp[i].push_back(p.second);
            }
            sort(comp[i].begin(),comp[i].end());
            comp[i].erase(unique(comp[i].begin(),comp[i].end()),comp[i].end());
            per[i].init(tree[i].size());
            rootnum[i].assign(tree[i].size(),0);
            for (int j=(int)tree[i].size()-1;j>=0;j--) {
                int r = lower_bound(comp[i].begin(),comp[i].end(),tree[i][j].second)-comp[i].begin();
                per[i].upd(r,1);
                rootnum[i][j] = per[i].roots.back();
            }
        }
    }
    int _getv(int i, int d, int rs, int re) {
        int t =lower_bound(tree[i].begin(),tree[i].end(),pii(d,-1))-tree[i].begin();
//        for (pii &p : tree[i]) {
//            printf("(%d, %d) ",p.first,p.second);
//        }
//        printf("%d!\n",d);
        if (t==tree[i].size()) return 0;
        rs = lower_bound(comp[i].begin(),comp[i].end(),rs)-comp[i].begin();
        re = upper_bound(comp[i].begin(),comp[i].end(),re)-comp[i].begin()-1;
        return per[i].getv(rs,re,rootnum[i][t]);
    }
    int getv(int s, int e, int d, int rs, int re) {
        s += key; e += key;
        int ans = 0;
        while(s<=e) {
            if (s&1) {
                ans += _getv(s,d,rs,re);
            }
            if (~e&1) {
                ans += _getv(e,d,rs,re);
            }
            s = (s+1)/2;
            e = (e-1)/2;
        }
        return ans;
    }
} itr, itl;

struct Idxtree {
    int tree[270000];
    const int key = 131072;
    void init() {
        memset(tree,0x3f,sizeof(tree));
    }
    void upd(int idx, int val) {
        idx += key;
        while(idx) {
            tree[idx] = min(tree[idx],val);
            idx/=2;
        }
    }
    int getv(int s, int e) {
        s += key;
        e += key;
        int ans = INF;
        while(s<=e) {
            if (s&1) ans = min(ans,tree[s]);
            if (~e&1) ans = min(ans,tree[e]);
            s = (s+1)/2;
            e = (e-1)/2;
        }
        return ans;
    }
} ith;

struct MIdxtree {
    int tree[270000];
    const int key = 131072;
    void init() {
        memset(tree,0,sizeof(tree));
    }
    void upd(int idx, int val) {
        idx += key;
        while(idx) {
            tree[idx] = max(tree[idx],val);
            idx/=2;
        }
    }
    int getv(int s, int e) {
        s += key;
        e += key;
        int ans = 0;
        while(s<=e) {
            if (s&1) ans = max(ans,tree[s]);
            if (~e&1) ans = max(ans,tree[e]);
            s = (s+1)/2;
            e = (e-1)/2;
        }
        return ans;
    }
} ithm;

int N;
vector<int> H;
int pr[100100], pl[100100];
int l[100100], r[100100];
map<int,int> loc;

void init(int _N, vector<int> _H) {
    N = _N;
    H = _H;
    ith.init();
    ithm.init();
    for (int i=0;i<N;i++) {
        ith.upd(i,H[i]);
        ithm.upd(i,H[i]);
        loc[H[i]] = i;
    }
    vector<int> st;
    for (int i=0;i<=N;i++) {
        int h = (i==N?INF:H[i]);
        while(!st.empty()&&H[st.back()]<h) {
            pr[st.back()] = i;
//            printf("(%d, %d): %d\n",st.back(),i-1,ith.getv(st.back(),i-1));
            r[st.back()] = H[st.back()] - ith.getv(st.back(),i-1);
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i=N-1;i>=-1;i--) {
        int h = (i==-1?INF:H[i]);
        while(!st.empty()&&H[st.back()]<h) {
            pl[st.back()] = i;
            l[st.back()] = H[st.back()] - ith.getv(i+1, st.back());
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i=0;i<N;i++) {
//        printf("%d: %d, %d, %d\n",i,min(l[i],r[i]),pl[i],pr[i]);
        itr.upd(i, {min(l[i],r[i]), pr[i]});
        itl.upd(i, {min(l[i],r[i]),pl[i]});
    }
    itl.calc();
    itr.calc();
}

int max_towers(int L, int R, int D) {
//    printf("%d, %d, %d\n",L,R,D);
    int ans = itr.getv(L, R, D, 0, N)+1;
    int maxih = ithm.getv(L,R);
    int m = loc[maxih];
    int minih = ith.getv(L,R);
    if (maxih-minih<D) return 1;
    {
        int s = m, e = R;
        while(s<=e) {
            int mid = (s+e)/2;
            if (ithm.getv(mid,R)-ith.getv(mid,R)>=D) s = mid+1;
            else e = mid-1;
        }
        ans -= itr.getv(s,R,D,R+1,N);
    }
    {
        int s = L, e = m;
        while(s<=e) {
            int mid = (s+e)/2;
            if (ithm.getv(L,mid)-ith.getv(L,mid)>=D) e = mid-1;
            else s = mid+1;
        }
        ans -= itl.getv(L,e,D,-1,L-1);
    }

    return ans;
}

Compilation message (stderr)

towers.cpp: In member function 'int Seg::_getv(int, int, int, int)':
towers.cpp:114:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if (t==tree[i].size()) return 0;
      |             ~^~~~~~~~~~~~~~~~

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