oj.uz

Submission #788588

# Submission time Handle Problem Language Result Execution time Memory
788588 2023-07-20T11:37:14 Z mosiashvililuka Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 2272 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 1972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4013 ms 2272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4097 ms 908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 1972 KB Time limit exceeded
2 Halted 0 ms 0 KB -