Submission #788588

#	Time	Username	Problem	Language	Result	Execution time	Memory
788588		mosiashvililuka	Radio Towers (IOI22_towers)	C++17	0 / 100	4097 ms	2272 KiB

towers

#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],pas,L,R,D,dp[100009],fen[200009],K[100009],HD[1000009],fen2[200009];
map <int, int> m;
map <int, int>::iterator it;
void init(int NN, std::vector<int> HH) {
    a=NN;
}
void upd(int q, int w){
    while(q<=200005){
        fen[q]=max(fen[q],w);
        q=q+(q&(-q));
    }
}
int read(int q){
    int sm=0;
    while(q>0){
        sm=max(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;
}
int max_towers(int LL, int RR, int DD) {
    pas=1;LL++;RR++;
    L=LL;R=RR;D=DD;
    for(i=1; i<=R-L+1; i++){
        f[i]=f[i+L-1];
    }
    a=R-L+1;

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

    zx=0;
    for(it=m.begin(); it!=m.end(); it++){
        zx++;
        (*it).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++){
        dp[i]=read2(HD[i])+1;
        zx=read(K[i]);
        upd2(K[i],zx);
        upd(HD[i],dp[i]);
    }

    for(i=1; i<=a; i++){
        pas=max(pas,dp[i]);
    }
    return pas;
}

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