Submission #1225962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225962		modwwe	Radio Towers (IOI22_towers)	C++20	100 / 100	572 ms	37044 KiB

towers

//#include "sphinx.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf=1e9;
const ll mod2 =1e9+7;
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,en;
int el = 19;
//const ll base=67;
int st[17][100001],st2[17][100001],a[100001];
struct ib
{
    int a,b;
};
vector<int> ok;
vector<ib> vc;
ib d[100001];
int b[100001];
struct segc
{
    int a,b,c,d;
};
int mer(int x,int y)
{
    if(a[x]>a[y])return y;
    return x;
}
int mer2(int x,int y)
{
    if(a[x]>a[y])return x;
    return y;
}
int gg(int l,int r)
{
    int k=log2(r-l+1);
    return mer(st[k][l],st[k][r-mask(k)+1]);
}
int ggb(int l,int r)
{
    int k=log2(r-l+1);
    return a[mer2(st2[k][l],st2[k][r-mask(k)+1])];
}
void hehe(int l,int r)
{
    if(l==r)return;
    int mid=gg(l,r);
    int dist=inf;
    bool okk=0;
    if(a[mid-1]<a[mid]&&mid!=1)okk=1;
    if(a[mid+1]<a[mid]&&mid!=n)okk=1;
    d[mid]= {l-1,r+1};
    if(!okk)
    {
        if(l!=1)
        {
            dist=ggb(l,mid-1);
        }
        if(r!=n)
        {
            dist=min(dist,ggb(mid+1,r));
        }
        ok.pb({dist-a[mid]});
        vc.pb({dist-a[mid],mid});
    }
    if(l!=mid)
        hehe(l,mid-1);
    if(mid!=r)
        hehe(mid+1,r);
}
struct scibidi
{
    segc t[400001];
    segc merc(segc a,segc b)
    {
        return {max(a.a,b.a),min(a.b,b.b),max({a.c,b.a-a.b,b.c}),max({a.d,b.d,a.a-b.b})};
    }
    void build(int node,int l,int r)
    {
        if(l==r)
        {
            t[node]= {a[l],a[l],-inf,-inf};
            return;
        }
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        t[node]=merc(t[node<<1],t[node<<1|1]);
    }
    segc get(int node,int l,int r,int l1,int r1)
    {
        if(l>=l1&&r<=r1)return t[node];
        int mid=l+r>>1;
        if(mid<l1)return get(node<<1|1,mid+1,r,l1,r1);
        if(mid>=r1)return get(node<<1,l,mid,l1,r1);
        return merc(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
} hihi;
bool cmp(ib a,ib b)
{
    return a.a>b.a;
}
struct ic
{
    int a,b,c;
};
struct ddcdc{int l,r;};
ddcdc cur[1700001];
struct perseg
{
    ic t[1700001];
    ic siuu(ic a,ic b)
    {
        return {min(a.a,b.a),max(a.b,b.b),a.c+b.c};
    }
    int upd(int u,int l,int r,int x)
    {
        int v=++dem2;
        if(l==r)
        {
            t[v]= {x,x,1};
            return v;
        }
        int mid=l+r>>1;
        cur[v]=cur[u];
        if(x<=mid)cur[v].l=upd(cur[u].l,l,mid,x);
        else cur[v].r=upd(cur[u].r,mid+1,r,x);
        t[v]=siuu(t[cur[v].l],t[cur[v].r]);
        return v;
    }
    ic get(int u,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1||u==0)return {inf,0,0};
        if(l>=l1&&r<=r1)return t[u];
        int mid=l+r>>1;
        return siuu(get(cur[u].l,l,mid,l1,r1),get(cur[u].r,mid+1,r,l1,r1));
    }
}seg;
void init(int N,vector<int> aa)
{
    n=N;
    for(int i=0; i<n; i++)
        a[i+1]=aa[i],st[0][i+1]=i+1,st2[0][i+1]=i+1;
    hihi.build(1,1,n);
    for(int i=1; i<=16; i++)
        for(int j=1; j+mask(i)-1<=n; j++)
            st[i][j]=mer(st[i-1][j],st[i-1][j+mask(i-1)]),
                     st2[i][j]=mer2(st2[i-1][j],st2[i-1][j+mask(i-1)]);
    hehe(1,n);
    sort(ok.begin(),ok.end());
    ok.erase(unique(ok.begin(),ok.end()),ok.end());
    sort(vc.begin(),vc.end(),cmp);
    seg.t[0]={inf,0,0};
    s3=0;
    l=0;
    for(int i=ok.size()-1;i>=0;i--)
    {
        while(l<vc.size()&&vc[l].a==ok[i])
        {
           s3=seg.upd(s3,1,n,vc[l].b);
            l++;
        }
        b[i]=s3;
    }
}
int max_towers(int l,int r,int dd)
{
    l++;
    r++;
    s4=inf;
    s5=0;
    dem=0;
    int hc=lower_bound(ok.begin(),ok.end(),dd)-ok.begin();
    ic x=seg.get(b[hc],1,n,l,r);
    s4=x.a;
    s5=x.b;
    dem=x.c;
    if(dem==0)
    {
        s2=gg(l,r);
        dem=1;
        if(s2!=l)
        {
            if(hihi.get(1,1,n,l,s2-1).c>=dd)dem++;
        }
        if(s2!=r)
        {
            s3=ggb(s2+1,r);
            if(hihi.get(1,1,n,s2+1,r).d>=dd)dem++;
        }
        return dem;
    }
    else
    {
        if(d[s4].a>=l)dem++;
        else
        {
            if(hihi.get(1,1,n,l,s4).c>=dd)dem++;
        }
        if(d[s5].b<=r)dem++;
        else
        {
            if(hihi.get(1,1,n,s5,r).d>=dd)dem++;
        }
        return dem;
    }
}

• 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