Submission #1096452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096452		quangnamoiracvl_ralaidecu	Global Warming (CEOI18_glo)	C++14	10 / 100	227 ms	15184 KiB

glo

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5, mod = 1e9;
 
int n,k,a[N],st[4*N], dp[N], dpv[N],l[N], b[N]; map<int,int> s;
 
void update(int id, int l, int r, int pos, int val){
    if(pos < l || pos > r) return;
    if(l == r){
       st[id] = val ;
       return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, pos, val);
    update(id*2+1, mid+1, r, pos, val);
    st[id] = max(st[id*2] , st[id*2+1]) ;
}
 
int get(int id, int l, int r, int u, int v){
    if(r < u || l > v) return 0;
    if(l >= u && r <= v) return st[id];
 
    int mid = (l+r)/2;
    return max(get(id*2, l, mid, u, v) , get(id*2+1, mid+1, r, u, v)) ;
}
 
signed main()   
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0); 
    cin >> n >> k; for ( int i = 1; i <= n; i++ ) 
      {
        cin >> a[i]; 
        s[a[i]] = 1;
      }
      s[k]++;
    int d = 0; 
    for ( auto v : s ) {
        d++;
        s[v.first] = d;
    }
    k = s[k];
    for ( int i = 1; i <= n; i++ ) {
        a[i] = s[a[i]];
        // yêu thảo nguyên vl
    }
    int ans = -1;
    for ( int i = 1; i <= n; i++ ) {
        dp[i] = get(1,1,d,1,a[i] - 1) + 1;
      ans = max( ans, dp[i]);
        update(1,1,d,a[i],dp[i]);
    }
  
    cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25