Submission #1262053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262053		dhuyyyy	Global Warming (CEOI18_glo)	C++20	58 / 100	2095 ms	15620 KiB

glo

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;

const int N = 2e5+5;
const int INF = 1e9;
const int MOD = 998244353;

int n,m,x,ans = 0;
int a[N],b[N],A[N],dp[N],t[N * 8],pre[N],LIS[N];
vector <int> v;
void update(int id,int l,int r,int pos,int val){
    if (r < pos || l > pos) return;
    if (l == r){
        t[id] = max(t[id],val);
        return;
    }
    int mid = (l + r) >> 1;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    t[id] = max(t[id*2],t[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
    if (r < u || l > v) return 0;
    if (u <= l && r <= v) return t[id];
    int mid = (l + r) >> 1;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int calc(int val){
    return lower_bound(v.begin(),v.end(),val) - v.begin();
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> x;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        A[i] = a[i] + x;
        v.push_back(a[i]);
        v.push_back(A[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m = (int)v.size();
    for (int i = 1; i <= n; i++) a[i] = calc(a[i]) + 1;
    for (int i = 1; i <= n; i++) A[i] = calc(A[i]) + 1;
    for (int i = 1; i <= n; i++){
        int j = lower_bound(b+1,b+1+ans,a[i]) - b;
        dp[i] = j;
        b[j] = a[i];
        ans = max(ans,j);
    }
    LIS[n] = 1;
    for (int i = 1; i <= n; i++) b[i] = 0;
    b[1] = a[n];
    int tmp = 1;
    for (int i = n - 1; i >= 1; i--){
        int j = tmp;
        while (j >= 1 && a[i] >= b[j]) j--;
        if (j == tmp) b[++tmp] = a[i];
        b[j + 1] = max(b[j + 1],a[i]);
        LIS[i] = j + 1;
    }
//    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
//    cout << '\n';
//    for (int i = 1; i <= n; i++) cout << dp[i] << ' ';
//    cout << '\n';
//    for (int i = 1; i <= n; i++) cout << A[i] << ' ';
//    cout << '\n';
    ans = 0;
    for (int i = 0; i < n; i++){
        update(1,1,m,a[i],dp[i]);
        int tmp = get(1,1,m,1,A[i+1]-1);
        ans = max(ans,tmp + LIS[i+1]);
//        cout << tmp << ' ' << LIS[i+1] << '\n';
    }
    cout << ans;
    return 0;
}

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