oj.uz

Submission #993527

# Submission time Handle Problem Language Result Execution time Memory
993527 2024-06-06T00:19:35 Z kkzyr Global Warming (CEOI18_glo) C++17
48 / 100
 863 ms 37988 KB 
#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;
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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4552 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4552 KB Output is correct
12 Correct 1 ms 4452 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4548 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4448 KB Output is correct
18 Correct 1 ms 4448 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4552 KB Output is correct
12 Correct 1 ms 4452 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4548 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4448 KB Output is correct
18 Correct 1 ms 4448 KB Output is correct
19 Correct 2 ms 4700 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 2 ms 4564 KB Output is correct
23 Correct 1 ms 4548 KB Output is correct
24 Correct 2 ms 4700 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 2 ms 4700 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 815 ms 37988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12720 KB Output is correct
2 Correct 138 ms 12628 KB Output is correct
3 Correct 131 ms 12628 KB Output is correct
4 Correct 74 ms 12680 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 66 ms 13000 KB Output is correct
7 Correct 105 ms 13396 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 20820 KB Output is correct
2 Correct 253 ms 20564 KB Output is correct
3 Incorrect 863 ms 37972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4552 KB Output is correct
12 Correct 1 ms 4452 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4548 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4448 KB Output is correct
18 Correct 1 ms 4448 KB Output is correct
19 Correct 2 ms 4700 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 2 ms 4564 KB Output is correct
23 Correct 1 ms 4548 KB Output is correct
24 Correct 2 ms 4700 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 2 ms 4700 KB Output is correct
27 Incorrect 815 ms 37988 KB Output isn't correct
28 Halted 0 ms 0 KB -