제출 #1310211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310211		Rares	송신탑 (IOI22_towers)	C++20	4 / 100	402 ms	53324 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/

const int MAXN=1e5+10;
const int LG=18;
const int MAXA=MAXN*(4+LG);
const int INF=2e9;

int n,a[MAXN],root[MAXN];
int t;
vector <int> d;
struct R{
    int rez,l,r;
};

struct AINT_PERSISTENT{
    struct node{
        int st,dr;
        int rez,lrez,rrez;
    }aint[MAXA];

    void init (){
        for (int i=0;i<MAXA;++i){
            aint[i]={0,0,0,INF,-1};
        }
    }

    void update (int node, int l, int r, int prev, int pos){
        if (l==r){
            aint[node].rez=1;
            aint[node].lrez=l;
            aint[node].rrez=r;
            return;
        }
        int mij=(l+r)/2;
        if (pos<=mij){
            aint[node].st=++t;
            aint[node].dr=aint[prev].dr;
            update (aint[node].st,l,mij,aint[prev].st,pos);
        }
        else{
            aint[node].dr=++t;
            aint[node].st=aint[prev].st;
            update (aint[node].dr,mij+1,r,aint[prev].dr,pos);
        }

        aint[node].rez=aint[aint[node].st].rez+aint[aint[node].dr].rez;
        aint[node].lrez=min (aint[aint[node].st].lrez,aint[aint[node].dr].lrez);
        aint[node].rrez=max (aint[aint[node].st].rrez,aint[aint[node].dr].rrez);
    }

    void update (int node, int prev, int pos){
        update (node,1,n,prev,pos);
    }

    R query (int node, int l, int r, int ql, int qr){
        if (r<ql or l>qr) return {0,INF,-1};
        if (ql<=l and r<=qr){
            return {aint[node].rez,aint[node].lrez,aint[node].rrez};
        }
        int mij=(l+r)/2;
        R rez1=query (aint[node].st,l,mij,ql,qr);
        R rez2=query (aint[node].dr,mij+1,r,ql,qr);
        R rez;
        rez.rez=rez1.rez+rez2.rez;
        rez.l=min (rez1.l,rez2.l);
        rez.r=max (rez1.r,rez2.r);
        return rez;
    }

    R query (int node, int l, int r){
        return query (node,1,n,l,r);
    }

}pst;


struct AINT{
    int aint[4*MAXN];
    void update (int node, int l, int r, int pos, int x){
        if (r<pos or l>pos) return;
        if (l==r){
            aint[node]=x;
            return;
        }
        int mij=(l+r)/2;
        update (2*node,l,mij,pos,x);
        update (2*node+1,mij+1,r,pos,x);

        aint[node]=max (aint[2*node],aint[2*node+1]);
    }

    void update (int pos, int x){
        update (1,1,n,pos,x);
    }

    int query (int node, int l, int r, int ql, int qr){
        if (r<ql or l>qr) return 0;
        if (ql<=l and r<=qr){
            return aint[node];
        }
        int mij=(l+r)/2;
        int rez1=query (2*node,l,mij,ql,qr);
        int rez2=query (2*node+1,mij+1,r,ql,qr);
        return max (rez1,rez2);
    }

    int query (int l, int r){
        return query (1,1,n,l,r);
    }
}max_st,l_st,r_st;

int get_pos (int dcrt){

    return lower_bound (d.begin (),d.end (), dcrt)-d.begin ();
}

int l[MAXN],r[MAXN],dif[MAXN];
map <int,int> di;
vector <int> g[MAXN];

void preclr (){
    stack <int> st;
    st.push (0);
    for (int i=1;i<=n;++i){
        while (a[i]<=a[st.top ()]) st.pop ();
        l[i]=st.top ();
        st.push (i);
    }
    while (!st.empty ()) st.pop ();
    st.push (n+1);
    for (int i=n;i>=1;--i){
        while (a[i]<=a[st.top ()]) st.pop ();
        r[i]=st.top ();
        st.push (i);
    }
}

void init (int N, vector <int> h){
    n=N;
    for (int i=0;i<n;++i) a[i+1]=h[i];
    preclr ();
    for (int i=1;i<=n;++i){
        max_st.update (i,a[i]);
    }
    vector <int> aux;
    for (int i=1;i<=n;++i){
        int lcrt=max_st.query (max (1,l[i]),i)-a[i];
        int rcrt=max_st.query (i,min (n,r[i]))-a[i];
        dif[i]=min (lcrt,rcrt);
        l_st.update (i,lcrt);
        r_st.update (i,rcrt);
        aux.push_back (dif[i]);
    }
    sort (aux.begin (),aux.end ());
    for(int i=0;i<aux.size ();++i){
        if (i==0 or aux[i]!=aux[i-1]){
            d.push_back (aux[i]);
        }
    }

    for (int i=0;i<d.size ();++i){
        di[d[i]]=i;
    }
    for (int i=1;i<=n;++i){
        g[di[dif[i]]].push_back (i);
    }


    pst.init ();
    root[d.size()]=0;
    for (int i=d.size ()-1;i>=0;--i){
        root[i]=++t;
        for (auto x:g[i]){
            pst.update (root[i],root[i+1],x);
        }
    }

}

int max_towers (int l, int r, int d){
    l++;
    r++;
    int crt=get_pos (d);
    R p=pst.query (root[crt],l,r);
    if (l<=p.l-1 and r_st.query (l,p.l-1)>=d) p.rez++;

    if (p.r+1<=r and l_st.query (p.r+1,r)>=d) p.rez++;
    return max (p.rez,1);
}

• Subtask 1: 4 / 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