Submission #638904

#TimeUsernameProblemLanguageResultExecution timeMemory
638904PietraFinancial Report (JOI21_financial)C++14
0 / 100
126 ms9752 KiB
    // n valores 
    // qr escolher m p apresentar - a dif de 2 adjs n pode ser maior que d 
    // o ultimo a ser mostrado é pm = n (o ultimo cara smp aparece)
    // score é o n° vzs q o at eh maior que o pref dele + 1 
    #include<bits/stdc++.h>
    #define esq (2*no)
    #define dir ((2*no)+1)
    #define meio ((i+j)>>1)
    #define int long long
    using namespace std ;
     
    // qual o 1o maior p cada cara - esquerda 
    const int inf = 1e13 ; 
    const int maxn = 3e5 + 5 ; 
     
    int n, mx[maxn], d, dp[maxn], dp_fim[maxn], v[maxn], esqq[maxn] ; 
    int tree[4*maxn] ; 
     
    struct SEG{

    void upd(int no, int i, int j, int pos, int val){
        if(i == j){
            tree[no] = max(tree[no], val) ; return ; 
        }
        if(pos <= meio) upd(esq, i, meio, pos, val) ; 
        else upd(dir, meio + 1, j, pos, val) ; 
        tree[no] = max(tree[esq], tree[dir]) ;  
    }

    void upd2(int no, int i, int j, int pos, int val){
        if(i == j){
            tree[no] = val ; return ; 
        }
        if(pos <= meio) upd2(esq, i, meio, pos, val) ; 
        else upd2(dir, meio + 1, j, pos, val) ; 
        tree[no] = max(tree[esq], tree[dir]) ;  
    }

    int query(int no, int i, int j, int a, int b){
        if(a > j || b < i) return 0 ; 
        if(b >= j && a <= i) return tree[no] ; 
        return max(query(esq, i, meio, a, b), query(dir, meio + 1, j, a, b)) ;   
    }

} Seg ; 
     
int32_t main(){

    cin >> n >> d ; 

    vector<int> vec ; 

    for(int i = 1 ; i <= n ; i++){
        cin >> v[i] ; 
        vec.push_back(v[i]) ; 
    }

    sort(vec.begin(), vec.end()) ; 

    for(int i = 1 ; i <= n ; i++) v[i] = lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin() + 1 ; 

    dp[0] = 0 ; 

    for(int i = 1 ; i <= n ; i++){
        if(v[i] > v[i-1]) dp[i] = dp[i-1] + 1 ; 
        else dp[i] = 1 ; 
    }

    v[n+1] = 0 ; 
    dp[n+1] = 0 ; 

    for(int i = n ; i > 0 ; i--){
        if(v[i] < v[i+1]) dp[i] = dp_fim[i+1] + 1 ; 
        else dp_fim[i] = 1 ; 
    }

    int ans = 0 ; 

    for(int i = 1 ; i <= n ; i++){
        ans = max({ans, dp[i] + dp_fim[i+1], dp[i-1] + dp_fim[i]}) ;
    }

    cout << ans << "\n" ; 

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...