Submission #989757

#	Time	Username	Problem	Language	Result	Execution time	Memory
989757		parlimoos	Global Warming (CEOI18_glo)	C++14	100 / 100	305 ms	12668 KiB

glo

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , x;
vector<int> cmp , a;
int seginf[800001][2] , seg[800001] , is[200000];
int dp[200000][2];
int o = 0;

void cmpInt(){
    sort(cmp.bg() , cmp.end());
    cmp.resize(int(unique(cmp.bg() , cmp.end()) - cmp.bg()));
    for(int &el : a) el = int(lb(cmp.bg() , cmp.end() , el) - cmp.bg());
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r , seg[i] = 0;
    if(l == r) is[l] = i;
    else{
        int c = (l + r - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
    }
}
void updSeg(int i , int val){
    while(i >= 1) seg[i] = max(seg[i] , val) , i >>= 1;
}
int getSeg(int l , int r , int i){
    if(r < l) return 0;
    if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i];
    if(seginf[i][1] >= l and seginf[i][0] <= r) return max(getSeg(l , r , i << 1) , getSeg(l , r , (i << 1) | 1));
    return 0;
}
void f(){
    buildSeg();
    for(int i = 0 ; i < n ; i++){
        dp[i][0] = getSeg(0 , a[i] - 1 , 1) + 1;
        updSeg(is[a[i]] , dp[i][0]);
    }
    buildSeg();
    for(int i = n - 1 ; i >= 0 ; i--){
        dp[i][1] = getSeg(a[i] + 1 , n - 1 , 1) + 1;
        updSeg(is[a[i]] , dp[i][1]);
    }
    buildSeg();
    for(int i = 0 ; i < n ; i++){
        int inx = int(lb(cmp.bg() , cmp.end() , cmp[a[i]] + x) - cmp.bg());
        o = max(o , getSeg(0 , inx - 1 , 1) + dp[i][1]);
        updSeg(is[a[i]] , dp[i][0]);
    }
    buildSeg();
    for(int i = n - 1 ; i >= 0 ; i--){
        int inx = int(ub(cmp.bg() , cmp.end() , cmp[a[i]] - x) - cmp.bg());
        o = max(o , getSeg(inx , n - 1 , 1) + dp[i][0]);
        // if(o == 6) cout << i << "!!\n";
        updSeg(is[a[i]] , dp[i][1]);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> x;
    for(int i = 0 ; i < n ; i++){
        cmp.pb(0);
        cin >> cmp.back();
        a.pb(cmp.back());
    }
    cmpInt() , f();
    cout << o;
}

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