Submission #1225954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225954		modwwe	Radio Towers (IOI22_towers)	C++20	44 / 100	4085 ms	29744 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];
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;
}
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);
    /**l=0;
    for(int i=1;i<=ok.size();i++)
    {
        while(l<vc.size()&&vc[l].a==ok[i-1])
        {
            s3=seg.upd(s3,1,n,vc[l].b);
        }
        b[i]=s3;
    }*/
}
int max_towers(int l,int r,int dd)
{
    l++;
    r++;
    s4=inf;
    s5=0;
    dem=0;
    for(auto x:vc)
        if(x.a>=dd&&x.b>=l&&x.b<=r)
        {
            dem++;
            s4=min(x.b,s4);
            s5=max(s5,x.b);
        }
    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: 0 / 14
• Subtask 5: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23