Submission #993524

#	Time	Username	Problem	Language	Result	Execution time	Memory
993524		kkzyr	Global Warming (CEOI18_glo)	C++17	0 / 100	721 ms	21136 KiB

glo

#include <iostream>
#include <algorithm>
#include <map>
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;
const int INF = 1e9 + 5;

int n, x;
int nums[MAX_N];

map<triple, 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;
    }
    for (int i = 1;i <= n;i++){
        lis[i] = INF;
    }
}

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]] = 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 = dp1[n];
    for (int i = 1;i <= n;i++){
        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';
            }
        }
        cout << '\n';
        */
        ans = max(ans, new_sum);
        update_pos(m[{nums[i], dp2[i], true}]);
    }
    cout << ans << '\n';
    return 0;
}

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