Submission #1158596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158596		Math4Life2020	Radio Towers (IOI22_towers)	C++20	60 / 100	4017 ms	10648 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 1e5; const ll K = 400; const ll INF = 1e18;
map<ll,array<ll,3>> mdn[Nm/K]; //D -> {start #, end #, # of terms}
//start down: go DUDUD...
map<ll,array<ll,3>> mup[Nm/K];
ll H0[Nm];

void pdn(ll T, vector<ll> v0, ll Dmin, bool isDn) {
    if (Dmin>=INF/2) {
        Dmin =INF/2;
    }
    //cout << "T,isDn="<<T<<","<<isDn<<"\n";
    //cout << "Dmin="<<Dmin<<"\n";
    ll Dc = INF;
    ll x2p = -INF; ll xp = INF; ll xc = INF; bool cdown = 1;
    //isDn -> first move is down
    if (!isDn) {
        x2p = INF; xp = -INF; xc = -INF; cdown = 0;
    }
    ll nfirst = -1;
    ll len = 0;
    for (ll x0: v0) {
        if (cdown) {
            if (x0<xc && (xp-x0)>=Dmin) {
                xc = x0;
                if ((xp-xc)>=Dmin) {
                    //cout << "into Dc: xp,x2p="<<xp<<","<<x2p<<"\n";
                    Dc = min(Dc,xp-x2p);
                    if (len==1) {
                        nfirst = xp;
                    }
                    len++;
                    x2p = xp; xp = xc; cdown = 0; xc = -INF;
                    //cout << "flipping; new (x2p,xp,xc)="<<x2p<<","<<xp<<","<<xc<<"\n";
                }
            } else if (x0>xp) {
                xp = x0; xc = INF;
                //cout << "1push down prev to "<<x0<<"\n";
            }
        } else {
            //cout << "x0,xp="<<x0<<","<<xp<<"\n";
            if (x0>xc && (x0-xp)>=Dmin) {
                xc = x0;
                if ((xc-xp)>=Dmin) {
                    Dc = min(Dc,x2p-xp);
                    if (len==1) {
                        nfirst = xp;
                    }
                    len++;
                    x2p = xp; xp = xc; cdown = 1; xc = INF;
                    //cout << "flipping; new (x2p,xp,xc)="<<x2p<<","<<xp<<","<<xc<<"\n";
                }
            } else if (x0<xp) {
                xp = x0; xc = -INF;
                //cout << "2push up prev to "<<x0<<"\n";
            }
        }
    }
    Dc = min(Dc,abs(x2p-xp));
    assert(Dc>=Dmin);
    if (Dmin>=(INF/2)) {
        assert(len<=1);
    }
    if (len==0) {
        if (isDn) {
            //cout << "creating mdn[INF]: "<<xc<<","<<xc<<","<<1<<"\n";
            mdn[T][INF]={xc,xc,1};
        } else {
            //cout << "creating mup[INF]: "<<xc<<","<<xc<<","<<1<<"\n";
            mup[T][INF]={xc,xc,1};
        }
    } else {
        if (len==1) {
            nfirst = xp;
        }
        if (isDn) {
            //cout << "creating mdn["<<Dc<<"]: "<<nfirst<<","<<xp<<","<<len<<"\n";
            mdn[T][Dc]={nfirst,xp,len};
        } else {
            //cout << "creating mdn["<<Dc<<"]: "<<nfirst<<","<<xp<<","<<len<<"\n";
            mup[T][Dc]={nfirst,xp,len};
        }
        if (len>1) {
            pdn(T,v0,Dc+1,isDn);
        }
    }
}

void init(int N, vector<int> H) {
    for (ll i=0;i<N;i++) {
        H0[i]=H[i];
    }
    for (ll T=0;T<(Nm/K);T++) {
        vector<ll> cnum;
        for (ll i=0;i<K;i++) {
            cnum.push_back(H0[i+T*K]);
        }
        pdn(T,cnum,0,1);
        pdn(T,cnum,0,0);
    }
}

struct seg {
    bool ifdn; //is first down?
    ll len; //number of terms
    ll x0,x1; //first and last terms
    seg(ll xc, bool bdn) {
        len = 1;
        ifdn = bdn;
        x0 = xc; x1 = xc;
    }
    seg(ll _x0, ll _x1, ll _len, bool _ifdn) {
        x0 = _x0; x1 = _x1; len = _len; ifdn = _ifdn;
    }
};

struct endp {
    ll vup,vdn,lup,ldn; 
    //vup: (min) value of the previous term (upon going up)
    //vdn: (max) value of the previous term (upon going down)
    //lup/ldn: number of DOWNS so far
    endp() {
        vup = -INF; lup = 0;
        vdn = INF; ldn = 0;
    }
    void fz(seg s0, ll D) {
        ll vup1 = vup; ll vdn1 = vdn; ll lup1 = lup; ll ldn1 = ldn;
        if (s0.ifdn) { //first step is going down aka DUDU...
            //vup: ...DUD so far
            pii ptest = {(lup+(s0.len+1)/2-1),s0.x1};
            if ((s0.len%2)==0) {
                //ends in U -> going down -> vdn
                if (ptest.first>ldn1) {
                    ldn1 = ptest.first; vdn1 = ptest.second;
                } else if (ptest.first==ldn1) {
                    vdn1 = max(vdn1,ptest.second);
                }
            } else {
                //ends in D -> going up -> vup
                if (ptest.first>lup1) {
                    lup1 = ptest.first; vup1 = ptest.second;
                } else if (ptest.first==lup1) {
                    vup1 = min(vup1,ptest.second);
                }
            }
            //vdn: ...UDU so far
            if ((vdn-s0.x0)>=D) {
                ptest = {(ldn+(s0.len+1)/2),s0.x1};
            } else {
                ptest = {(ldn-1+(s0.len+1)/2),s0.x1};
            }
            //copy and paste rest of code
            if ((s0.len%2)==0) {
                //ends in U -> going down -> vdn
                if (ptest.first>ldn1) {
                    ldn1 = ptest.first; vdn1 = ptest.second;
                } else if (ptest.first==ldn1) {
                    vdn1 = max(vdn1,ptest.second);
                }
            } else {
                //ends in D -> going up -> vup
                if (ptest.first>lup1) {
                    lup1 = ptest.first; vup1 = ptest.second;
                } else if (ptest.first==lup1) {
                    vup1 = min(vup1,ptest.second);
                }
            }
        } else { //first step is going up aka UDUD...
            //vup: ...DUD so far
            pii ptest;
            if ((s0.x0-vup)>=D) {
                ptest = {lup+(s0.len)/2,s0.x1};
            } else {
                ptest = {lup+(s0.len)/2-1,s0.x1};
            }
            //copy and paste rest of code
            if ((s0.len%2)==1) {
                //ends in U -> going down -> vdn
                if (ptest.first>ldn1) {
                    ldn1 = ptest.first; vdn1 = ptest.second;
                } else if (ptest.first==ldn1) {
                    vdn1 = max(vdn1,ptest.second);
                }
            } else {
                //ends in D -> going up -> vup
                if (ptest.first>lup1) {
                    lup1 = ptest.first; vup1 = ptest.second;
                } else if (ptest.first==lup1) {
                    vup1 = min(vup1,ptest.second);
                }
            }
            //vdn: ...UDU so far
            ptest = {ldn+s0.len/2,s0.x1};
            //copy and paste rest of code
            if ((s0.len%2)==1) {
                //ends in U -> going down -> vdn
                if (ptest.first>ldn1) {
                    ldn1 = ptest.first; vdn1 = ptest.second;
                } else if (ptest.first==ldn1) {
                    vdn1 = max(vdn1,ptest.second);
                }
            } else {
                //ends in D -> going up -> vup
                if (ptest.first>lup1) {
                    lup1 = ptest.first; vup1 = ptest.second;
                } else if (ptest.first==lup1) {
                    vup1 = min(vup1,ptest.second);
                }
            }
        }
        vup = vup1; vdn = vdn1; lup = lup1; ldn = ldn1;
    }
    ll getans() {
        return max(lup,ldn);
    }
    void print() {
        cout << "vup,lup="<<vup<<","<<lup<<"; vdn,ldn="<<vdn<<","<<ldn<<"\n";
    }
};

endp maxp(endp s0, endp s1) {
    endp s2;
    if (s0.ldn!=s1.ldn) {
        if (s0.ldn>s1.ldn) {
            s2.ldn=s0.ldn;
            s2.vdn=s0.vdn;
        } else {
            s2.ldn=s1.ldn;
            s2.vdn=s1.vdn;
        }
    } else {
        s2.ldn=s0.ldn;
        s2.vdn=max(s0.vdn,s1.vdn);
    }
    if (s0.lup!=s1.lup) {
        if (s0.lup>s1.lup) {
            s2.lup=s0.lup;
            s2.vup=s0.vup;
        } else {
            s2.lup=s1.lup;
            s2.vup=s1.vup;
        }
    } else {
        s2.lup=s0.lup;
        s2.vup=min(s0.vup,s1.vup);
    }
    return s2;
}

int max_towers(int L, int R, int D) {
    ll kl = L/K; ll kr = R/K;
    endp s0;
    if (kl==kr) {
        for (ll i=L;i<=R;i++) {
            endp s1 = s0; endp s2 = s0;
            s1.fz(seg(H0[i],0),D);
            s2.fz(seg(H0[i],1),D);
            s0 = maxp(s1,s2);
            // cout << "after a new number: \n";
            // s0.print();
        }
    } else {
        for (ll i=L;i<K*(1+kl);i++) {
            endp s1 = s0; endp s2 = s0;
            s1.fz(seg(H0[i],0),D);
            s2.fz(seg(H0[i],1),D);
            s0 = maxp(s1,s2);
        }
        for (ll i=(1+kl);i<kr;i++) {
            endp s1 = s0; endp s2 = s0;
            auto A0 = (*mdn[i].lower_bound(D)).second;
            s1.fz(seg(A0[0],A0[1],A0[2],1),D);
            auto A1 = (*mup[i].lower_bound(D)).second;
            s2.fz(seg(A1[0],A1[1],A1[2],0),D);
            s0 = maxp(s1,s2);
        }
        for (ll i=(kr*K);i<=R;i++) {
            endp s1 = s0; endp s2 = s0;
            s1.fz(seg(H0[i],0),D);
            s2.fz(seg(H0[i],1),D);
            s0 = maxp(s1,s2);
        }
    }
    return s0.getans();
}

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