Submission #788769

#	Time	Username	Problem	Language	Result	Execution time	Memory
788769		mosiashvililuka	Radio Towers (IOI22_towers)	C++17	56 / 100	1103 ms	21596 KiB

towers

#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
const int N=2000000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],pas,L,R,D,seg[400009],l,r,z,za,PI,bo[100009],VAL[100009],pr[100009],counter,fen[200009],fen2[200009],K[100009],HD[1000009],lf[100009],rg[100009],aris[100009];
int segLF[400009],segRG[400009],segaris[400009];
map <int, int> m;
map <int, int>::iterator TA;
vector <pair <int, int> > ANS;
multiset <int> s;
multiset <int>::iterator it,tt;
multiset <pair <int, int> > S;
multiset <pair <int, int> >::iterator IT,TT;
pair <int, int> P[100009];
//
void upd(int q, int w){
    q=200003-q;
    while(q<=200005){
        fen[q]=min(fen[q],w);
        q=q+(q&(-q));
    }
}
int READ(int q){
    q=200003-q;
    int sm=200007;
    while(q>0){
        sm=min(sm,fen[q]);
        q=q-(q&(-q));
    }
    return sm;
}

void upd2(int q, int w){
    q=200003-q;
    while(q<=200005){
        fen2[q]=max(fen2[q],w);
        q=q+(q&(-q));
    }
}
int read2(int q){
    q=200003-q;
    int sm=0;
    while(q>0){
        sm=max(sm,fen2[q]);
        q=q-(q&(-q));
    }
    return sm;
}


void upd3(int q, int w){
    while(q<=200005){
        fen[q]=max(fen[q],w);
        q=q+(q&(-q));
    }
}
int read3(int q){
    int sm=0;
    while(q>0){
        sm=max(sm,fen[q]);
        q=q-(q&(-q));
    }
    return sm;
}
//
void read(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,seg[rr]);
        return;
    }
    read(q,(q+w)/2,rr*2);
    read((q+w)/2+1,w,rr*2+1);
}

void readLF(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,segLF[rr]);
        return;
    }
    readLF(q,(q+w)/2,rr*2);
    readLF((q+w)/2+1,w,rr*2+1);
}
void readRG(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=min(z,segRG[rr]);
        return;
    }
    readRG(q,(q+w)/2,rr*2);
    readRG((q+w)/2+1,w,rr*2+1);
}
void readaris(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,segaris[rr]);
        return;
    }
    readaris(q,(q+w)/2,rr*2);
    readaris((q+w)/2+1,w,rr*2+1);
}
//
void UPD(int i){
    int D;
    multiset <int>::iterator it,tt;
    multiset <pair <int, int> >::iterator IT,TT;
    tt=s.lower_bound(i);
    tt++;


    if(tt==s.end()){
        R=a+1;
    }else{
        R=(*tt);
    }
    it=s.lower_bound(i);
    if(it==s.begin()){
        L=0;
    }else{
        it--;
        L=(*it);
    }
    L++;R--;



    z=0;
    l=i+1;r=R;
    if(l<=r) read(1,za,1);
    if(r==a) z=N;
    e=z;
    z=0;
    l=L;r=i-1;
    if(l<=r) read(1,za,1);
    if(l==1) z=N;
    e=min(e,z);
    S.erase({VAL[i],i});
    S.insert({e-f[i]+1,i});
    VAL[i]=e-f[i]+1;
}
void init(int NN, std::vector<int> HH) {
    a=NN;
    for(i=1; i<=a; i++){
        f[i]=HH[i-1];
    }
}

int max_towers(int LL, int RR, int DD) {
    counter++;
    if(counter==1){
        za=1;D=DD;
        while(za<a) za*=2;
        for(i=1; i<=a; i++){
            seg[za+i-1]=f[i];
        }
        for(i=za-1; i>=1; i--){
            seg[i]=max(seg[i*2],seg[i*2+1]);
        }

        for(i=1; i<=a; i++){
            PI++;P[PI]={f[i],i};
        }
        sort(P+1,P+PI+1);


        for(ii=1; ii<=PI; ii++){
            i=P[ii].second;
            tt=s.lower_bound(i);
            if(tt==s.end()){
                R=a+1;
            }else{
                R=(*tt);
            }
            it=s.lower_bound(i);
            if(it==s.begin()){
                L=0;
            }else{
                it--;
                L=(*it);
            }
            L++;R--;

            e=0;
            z=0;
            l=i+1;r=R;
            if(l<=r) read(1,za,1);
            if(r==a) z=N;
            if(z<f[i]+D){
                e++;
            }
            z=0;
            l=L;r=i-1;
            if(l<=r) read(1,za,1);
            if(l==1) z=N;
            if(z<f[i]+D){
                e++;
            }
            if(e>0) continue;
            //cout<<i<<" "<<z<<" "<<f[i]<<" "<<D<<"\n";
            s.insert(i);bo[i]=1;
        }


        for(i=1; i<=a; i++){
            pr[i]=pr[i-1]+bo[i];
        }
        /*for(i=1; i<=a; i++){
            cout<<pr[i]<<" pr ";
        }
        cout<<"\n";*/


        //
        m.clear();
        for(i=1; i<=a; i++){
            m[f[i]]=1;m[f[i]+D]=1;
        }
        zx=0;
        for(TA=m.begin(); TA!=m.end(); TA++){
            zx++;
            (*TA).second=zx;
        }

        for(i=1; i<=a; i++){
            HD[i]=m[f[i]+D];
            K[i]=m[f[i]];
        }

        for(i=1; i<=a; i++){
            lf[i]=read2(HD[i]);
            upd2(K[i],i);
        }

        /*for(i=1; i<=a; i++){
            cout<<lf[i]<<" lf ";
        }
        cout<<"\n";*/

        for(i=0; i<=200007; i++){
            fen[i]=a+1;
        }
        for(i=a; i>=1; i--){
            rg[i]=READ(HD[i]);
            upd(K[i],i);
        }

        for(i=1; i<=a; i++){
            segLF[za+i-1]=lf[i];
        }

        for(i=za-1; i>=1; i--){
            segLF[i]=max(segLF[i*2],segLF[i*2+1]);
        }

        for(i=1; i<=a; i++){
            segRG[za+i-1]=rg[i];
        }
        for(i=za-1; i>=1; i--){
            segRG[i]=min(segRG[i*2],segRG[i*2+1]);
        }



        //return 0;

        for(i=0; i<=200007; i++){
            fen[i]=fen2[i]=0;
        }
        for(i=1; i<=a; i++){
            aris[i]=read2(HD[i]);
            zx=read3(K[i]);
            /*cout<<i<<" "<<zx<<"\n";
            cout<<K[i]<<" "<<HD[i]<<"\n";*/
            upd2(K[i],zx);
            upd3(HD[i],i);
        }
        //return 0;

        for(i=1; i<=a; i++){
            segaris[za+i-1]=aris[i];
        }
        for(i=za-1; i>=1; i--){
            segaris[i]=max(segaris[i*2],segaris[i*2+1]);
        }
        //return 0;
    }











    //




    pas=1;LL++;RR++;
    L=LL;R=RR;D=DD;
    if(L==R) return 1;

    zx=pr[R]-pr[L-1];
    //cout<<zx<<"\n";
    it=s.lower_bound(L);

    l=L;r=lf[(*it)]-1;z=a+2;
    if(l<=r) readRG(1,za,1);
    if(z<(*it)) zx++;

    it=s.lower_bound(R+1);
    if(it!=s.end()){
        it--;

        l=rg[(*it)]+1;r=R;z=0;
        if(l<=r) readLF(1,za,1);
        if((*it)<z) zx++;
    }

    pas=max(pas,zx);

    //da-check-e 2-ic tu sheidzleba

    l=L;r=R;z=0;
    readaris(1,za,1);
    if(z>=L) pas=max(pas,2);
    return pas;
}

Compilation message (stderr)

towers.cpp: In function 'void UPD(int)':
towers.cpp:105:9: warning: unused variable 'D' [-Wunused-variable]
  105 |     int D;
      |         ^

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