Submission #1098054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098054		azberjibiou	Radio Towers (IOI22_towers)	C++17	100 / 100	1083 ms	59844 KiB

towers

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=500005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
struct segtree{
    pii seg[4*mxN];
    pii mrg(pii a, pii b){
        return pii(min(a.fi, b.fi), max(a.se, b.se));
    }
    void init(int idx, int s, int e, vector <int> &v){
        if(s==e){
            seg[idx]=pii(v[s], v[s]);
            return;
        }
        int mid=(s+e)/2;
        init(2*idx, s, mid, v);
        init(2*idx+1, mid+1, e, v);
        seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
    }
    pii solv(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return pii(MOD, -MOD);
        if(s2<=s1 && e1<=e2) return seg[idx];
        int mid=(s1+e1)/2;
        return mrg(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
    }
};
struct node{
    int val;
    int l, r;
    node() : val(), l(), r() {}
    node(int val, int l, int r) : val(val), l(l), r(r) {}
};
struct pst{
    vector <node> tree;
    int root[100010]={};
    int sz=1, L, R;
    void init_s(int a, int b){
        tree.resize(2300000);
        root[0]=sz++;
        L=a, R=b;
        init_t(root[0], L, R);
    }
    void init_t(int idx, int s, int e){
        if(s==e) return;
        int mid=(s+e)/2;
        tree[idx].l=sz++;
        init_t(sz-1, s, mid);
        tree[idx].r=sz++;
        init_t(sz-1, mid+1, e);
    }
    void upd_s(int now, int pos){
        root[now]=sz++;
        upd_t(root[now], root[now-1], L, R, pos);
    }
    void upd_t(int idx1, int idx2, int s, int e, int pos){
        tree[idx1].val=tree[idx2].val;
        tree[idx1].val++;
        if(s==e) return;
        int mid=(s+e)/2;
        if(pos<=mid) tree[idx1].l=sz++;
        else tree[idx1].r=sz++;
        if(pos<=mid) upd_t(sz-1, tree[idx2].l, s, mid, pos), tree[idx1].r=tree[idx2].r;
        else upd_t(sz-1, tree[idx2].r, mid+1, e, pos), tree[idx1].l=tree[idx2].l;
    }
    int solv_s(int rt, int s, int e){
        return solv_t(root[rt], L, R, s, e);
    }
    int solv_t(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return 0;
        if(s2<=s1 && e1<=e2) return tree[idx].val;
        int mid=(s1+e1)/2;
        return solv_t(tree[idx].l, s1, mid, s2, e2)+solv_t(tree[idx].r, mid+1, e1, s2, e2);
    }
    int bin_searchl_t(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return 0;
        if(s1==e1){
            return (tree[idx].val==1 ? s1 : 0);
        }
        if(s2<=s1 && e1<=e2){
            if(tree[idx].val!=0){
                int mid=(s1+e1)/2;
                int lres=bin_searchl_t(tree[idx].l, s1, mid, s2, e2);
                if(lres!=0) return lres;
                return bin_searchl_t(tree[idx].r, mid+1, e1, s2, e2);
            }
            else return 0;
        }
        int mid=(s1+e1)/2;
        int lres=bin_searchl_t(tree[idx].l, s1, mid, s2, e2);
        if(lres!=0) return lres;
        return bin_searchl_t(tree[idx].r, mid+1, e1, s2, e2);
    }
    int bin_searchr_t(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return 0;
        if(s1==e1){
            return (tree[idx].val==1 ? s1 : 0);
        }
        if(s2<=s1 && e1<=e2){
            if(tree[idx].val!=0){
                int mid=(s1+e1)/2;
                int rres=bin_searchr_t(tree[idx].r, mid+1, e1, s2, e2);
                if(rres!=0) return rres;
                return bin_searchr_t(tree[idx].l, s1, mid, s2, e2);
            }
            else return 0;
        }
        int mid=(s1+e1)/2;
        int rres=bin_searchr_t(tree[idx].r, mid+1, e1, s2, e2);
        if(rres!=0) return rres;
        return bin_searchr_t(tree[idx].l, s1, mid, s2, e2);
    }
    int bin_searchl_s(int rt, int s, int e){
        return bin_searchl_t(root[rt], L, R, s, e);
    }
    
    int bin_searchr_s(int rt, int s, int e){
        return bin_searchr_t(root[rt], L, R, s, e);
    }
};
int N, Q;
int A[mxN];
int qry[mxN][3];
int F[mxN];
vector <pii> Dp, Dm;
/*
void input(){
    cin >> N >> Q;
    A[0]=-1e9-10, A[1]=1e9+10;
    for(int i=2;i<=N+1;i++) cin >> A[i];
    A[N+2]=1e9+10, A[N+3]=-1e9-10;
    for(int i=1;i<=Q;i++){
        int l, r, d;
        cin >> l >> r >> d;
        qry[i][0]=l;
        qry[i][1]=r;
        qry[i][2]=d;
    }
}
*/
segtree T1;
void make_F(){
    vector <int> v(N+4);
    for(int i=0;i<=N+3;i++) v[i]=A[i];
    T1.init(1, 0, N+3, v);
    stack <int> stk;
    stk.push(1);
    for(int i=2;i<=N+1;i++){
        while(A[stk.top()]<A[i]) stk.pop();
        if(A[i]<A[i-1] || A[i]<A[i+1]) continue;
        int mini=(stk.top()==i-1 ? MOD : T1.solv(1, 0, N+3, stk.top()+1, i-1).fi);
        F[i]=A[i]-mini;
        stk.push(i);
    }
    while(stk.size()) stk.pop();

    stk.push(N+2);
    for(int i=N+1;i>=2;i--){
        while(A[stk.top()]<A[i]) stk.pop();
        if(A[i]<A[i-1] || A[i]<A[i+1]) continue;
        int mini=(stk.top()==i+1 ? MOD : T1.solv(1, 0, N+3, i+1, stk.top()-1).fi);
        F[i]=min(F[i], A[i]-mini);
        stk.push(i);
    }
    while(stk.size()) stk.pop();

    stk.push(0);
    for(int i=2;i<=N+1;i++){
        while(A[stk.top()]>A[i]) stk.pop();
        if(A[i]>A[i-1] || A[i]>A[i+1]) continue;
        int maxi=(stk.top()==i-1 ? -MOD : T1.solv(1, 0, N+3, stk.top()+1, i-1).se);
        F[i]=maxi-A[i];
        stk.push(i);
    }

    stk.push(N+3);
    for(int i=N+1;i>=2;i--){
        while(A[stk.top()]>A[i]) stk.pop();
        if(A[i]>A[i-1] || A[i]>A[i+1]) continue;
        int maxi=(stk.top()==i+1 ? -MOD : T1.solv(1, 0, N+3, i+1, stk.top()-1).se);
        F[i]=min(F[i], maxi-A[i]);
        F[i]*=-1;
        stk.push(i);
    }
    //for(int i=1;i<=N;i++) printf("F[%d]=%d\n", i, F[i+1]);
    for(int i=2;i<=N+1;i++) if(F[i]>0) Dp.emplace_back(F[i], i);
    for(int i=2;i<=N+1;i++) if(F[i]<0) Dm.emplace_back(-F[i], i);
    sort(all(Dp), [](pii a, pii b){return a>b;});
    sort(all(Dm), [](pii a, pii b){return a>b;});
    /*
    for(auto [x, y] : Dp) printf("(%d %d) ", x, y);
    printf("\n");
    for(auto [x, y] : Dm) printf("(%d %d) ", x, y);
    printf("\n");
    */
}
pst T2, T3;
void make_tree(){
    T2.init_s(2, N+1);
    for(int i=0;i<Dp.size();i++){
        T2.upd_s(i+1, Dp[i].se);
    }
    T3.init_s(2, N+1);
    for(int i=0;i<Dm.size();i++){
        T3.upd_s(i+1, Dm[i].se);
    }
}
void init(int n, vector <int> v){
    N=n;
    A[0]=-1e9-10, A[1]=1e9+10;
    for(int i=2;i<=N+1;i++) A[i]=v[i-2];
    A[N+2]=1e9+10, A[N+3]=-1e9-10;
    make_F();
    make_tree();
}
int max_towers(int l, int r, int d){
    l+=2, r+=2;
    int lp=N+3, lm=N+3, rp=0, rm=0, mcnt=0, pcnt=0;

    int mxidx, mnidx;
    mxidx=lower_bound(all(Dp), pii(d, 0), [](pii a, pii b){return a>b;})-Dp.begin();
    mnidx=lower_bound(all(Dm), pii(d, 0), [](pii a, pii b){return a>b;})-Dm.begin();
    pcnt=T2.solv_s(mxidx, l, r);
    mcnt=T3.solv_s(mnidx, l, r);
    if(pcnt!=0){
        rp=T2.bin_searchr_s(mxidx, l, r);
        lp=T2.bin_searchl_s(mxidx, l, r);
        /*
        int s=l, e=r+1;
        while(s!=e){
            int mid=(s+e)/2;
            if(T2.solv_s(mxidx, mid, r)==0) e=mid;
            else s=mid+1;
        }
        rp=s-1;
        s=l, e=r;
        while(s!=e){
            int mid=(s+e)/2;
            if(T2.solv_s(mxidx, l, mid)==0) s=mid+1;
            else e=mid;
        }
        lp=s;
        */
    }
    if(mcnt!=0){
        rm=T3.bin_searchr_s(mnidx, l, r);
        lm=T3.bin_searchl_s(mnidx, l, r);
        /*
        int s=l, e=r+1;
        while(s!=e){
            int mid=(s+e)/2;
            if(T3.solv_s(mnidx, mid, r)==0) e=mid;
            else s=mid+1;
        }
        rm=s-1;
        s=l, e=r;
        while(s!=e){
            int mid=(s+e)/2;
            if(T3.solv_s(mnidx, l, mid)==0) s=mid+1;
            else e=mid;
        }
        lm=s;
        */
    }
    /*
    for(int i=l;i<=r;i++){
        if(F[i]>=d) pcnt++, rp=max(rp, i), lp=min(lp, i);
        if(F[i]<=-d) mcnt++, rm=max(rm, i), lm=min(lm, i);
    }
    */
    if(rp!=0 && rp>=rm){
        bool ok=false;
        if(rp!=r && T1.solv(1, 0, N+3, rp+1, r).fi<=A[rp]-d) ok=true;
        if(ok) mcnt++;
    }
    if(lp!=N+3 && lp<=lm){
        bool ok=false;
        if(lp!=l && T1.solv(1, 0, N+3, l, lp-1).fi<=A[lp]-d) ok=true;
        if(ok) mcnt++;
    }
    return (mcnt<=1 ? 1 : mcnt);
}
/*
int main()
{
    gibon
    input();
    make_F();
    make_tree();
    for(int i=1;i<=Q;i++){
        printf("%d\n", max_towers(qry[i][0], qry[i][1], qry[i][2]));
    }
} 
*/

Compilation message (stderr)

towers.cpp: In function 'void make_tree()':
towers.cpp:211:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |     for(int i=0;i<Dp.size();i++){
      |                 ~^~~~~~~~~~
towers.cpp:215:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |     for(int i=0;i<Dm.size();i++){
      |                 ~^~~~~~~~~~

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