제출 #993530

#제출 시각아이디문제언어결과실행 시간메모리
993530kkzyrGlobal Warming (CEOI18_glo)C++17
100 / 100
979 ms40024 KiB
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

struct triple{
    int start_number;
    int dp_value;
    bool still_exists;
};

bool cmp(triple t1, triple t2){
    if (t1.start_number < t2.start_number){
        return true;
    }
    if (t1.start_number > t2.start_number){
        return false;
    }
    if (t1.dp_value > t2.dp_value){
        return true;
    }
    if (t1.dp_value < t2.dp_value){
        return false;
    }
    return false;
}

const int MAX_SQRT_N = 1e3;
const int MAX_N = 2e5 + 1;
const int INF = 1e9 + 5;

int n, x;
int nums[MAX_N];

map<triple, set<int>, decltype(&cmp)> m(cmp);

int num_values;
triple values[MAX_N];

int lis[MAX_N];
int dp1[MAX_N];
int dp2[MAX_N];

int block_size, num_blocks;
int which_block[MAX_N];
int block_start[MAX_SQRT_N];
int block_end[MAX_SQRT_N];
int block_max[MAX_SQRT_N];

void input(){
    cin >> n >> x;
    for (int i = 1;i <= n;i++){
        cin >> nums[i];
    }
}

int binary_search(int key){
    int lo = 1;
    int hi = n;
    int ans = 0;
    while (lo <= hi){
        int mid = (lo + hi)/2;
        if (lis[mid] < key){
            ans = mid;
            lo = mid + 1;
        }
        else{
            hi = mid - 1;
        }
    }
    return ans;
}

int binary_search2(int key){
    int lo = 1;
    int hi = n;
    int ans = 0;
    while (lo <= hi){
        int mid = (lo + hi)/2;
        if (lis[mid] > key and lis[mid] != INF){
            ans = mid;
            lo = mid + 1;
        }
        else{
            hi = mid - 1;
        }
    }
    return ans;
}

void lis1(){
    for (int i = 1;i <= n;i++){
        lis[i] = INF;
    }
    for (int i = 1;i <= n;i++) {
        int key = nums[i];
        int index = binary_search(key);
        lis[index + 1] = key;
        dp1[i] = index + 1;
    }
}

void lis2(){
    for (int i = 1;i <= n;i++){
        lis[i] = INF;
    }
    for (int i = n;i >= 1;i--) {
        int key = nums[i];
        int index = binary_search2(key);
        lis[index + 1] = key;
        dp2[i] = index + 1;
    }
}

void process_input(){
    for (int i = 1;i <= n;i++){
        num_values += 1;
        values[num_values] = {nums[i], dp2[i], true};
    }
    sort(values, values + n + 1, cmp);
    for (int i = 1;i <= n;i++){
        m[values[i]].insert(i);
    }
}

void preprocess(){
    for (int i = 1;i * i <= n;i++){
         block_size = i;
    }
    num_blocks = n/block_size;
    if (n % block_size != 0){
        num_blocks += 1;
    }
    for (int i = 1;i <= num_blocks;i++){
        block_start[i] = (i - 1) * block_size + 1;
        block_end[i] = min(i * block_size, n);
        for (int j = block_start[i];j <= block_end[i];j++){
            which_block[j] = i;
            block_max[i] = max(block_max[i], values[j].dp_value);
        }
    }
}

void update_pos(int i){
    values[i].still_exists = false;
    int block = which_block[i];
    block_max[block] = 0;
    for (int j = block_start[block];j <= block_end[block];j++){
        if (values[j].still_exists){
            block_max[block] = max(block_max[block], values[j].dp_value);
        }
    }
}

int range_max(int key){
    int ans = 0;
    for (int i = 1;i <= num_blocks;i++){
        int start = block_start[i];
        int end = block_end[i];
        if (values[start].start_number > key){
            ans = max(ans, block_max[i]);
        }
        else if (values[end].start_number > key){
            for (int j = start;j <= end;j++){
                if (values[j].still_exists and values[j].start_number > key){
                    ans = max(ans, values[j].dp_value);
                }
            }
        }
    }
    return ans;
}

int main(){
    input();
    lis1();
    lis2();
    process_input();
    preprocess();
    int ans = 0;
    for (int i = 1;i <= n;i++){
        update_pos(*(m[{nums[i], dp2[i], true}].begin()));
        m[{nums[i], dp2[i], true}].erase(*(m[{nums[i], dp2[i], true}].begin()));
        int new_sum = dp1[i] + range_max(nums[i] - x);
        /*
        for (int j = 1;j <= n;j++){
            if (values[j].still_exists){
                cout << values[j].start_number << ' ' << values[j].dp_value << '\n';
            }
        }
        */
        ans = max(ans, new_sum);
    }
    cout << ans << '\n';
    return 0;
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...