Submission #622276

#	Time	Username	Problem	Language	Result	Execution time	Memory
622276		jophyyjh	Global Warming (CEOI18_glo)	C++14	100 / 100	647 ms	43072 KiB

glo

/**
 * Notes during contest.
 * 
 * ------ A ------
 * Looks like a dp.
 * 
 * ------ B ------
 * I think i've seen sth similar on luogu. First, let's assume that d >= 0 and i'll
 * use the words "increase" & "decrease". If we wanna increase an interval by d, we
 * can greedily increase a suffix (instead of just an interval in the middle). If we
 * are to decrease an interval by d, we can greedily decrease a prefix. The two cases
 * are symmetric, so we can assume that one always increase a suffix by 0 <= d <= x.
 * And, if we're increasing a suffix, why don't we just do d=x? The rest is quite
 * straight-forward.
 * 
 * ------ C ------
 * For k_j = 0, we have to find the num of times each interval appeared. This can be
 * effectively done with str hashing. [S3] solved. [S1] is just brute-force: we can
 * do a O(n^2) for loop, iterating over all pairs of starting pos, naively comparing
 * the dist. of 2 substr. [S2] is a O(n^2) comparison between pairs of VALUES and
 * apply a difference array.
 * We're only looking for the num of mismatches. Let's compress the values (a_i:
 * 10^9 -> 10^4).
 * 
 * Time Complexity 1: O()
 * Time Complexity 2: O(n * log(n))
 * Time Complexity 3: O(n^2 + q) ([S1-2]), O(n)    (non-deterministic hashing)
 * Implementation 1             (Full solution, n * log(n) dp for LIS)
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
const int_t INF = 0x3f3f3f3f3f3f3f;
 
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int_t n, x;
    std::cin >> n >> x;
    vec values(n);
    for (int_t k = 0; k < n; k++)
        std::cin >> values[k];
    
 
    vec left(n), right(n), min_end(n, INF);
    for (int_t k = 0; k < n; k++) {
        int_t t = -1;
        for (int_t step = n / 2 + 1; step >= 1; step /= 2) {
            while (t + step < n && values[k] > min_end[t + step])
                t += step;
        }
        min_end[t + 1] = values[k], left[k] = t + 2;
    }
    min_end.assign(n, -INF);
    for (int_t k = n - 1; k >= 0; k--) {
        int_t t = -1;
        for (int_t step = n / 2 + 1; step >= 1; step /= 2) {
            while (t + step < n && values[k] < min_end[t + step])
                t += step;
        }
        min_end[t + 1] = values[k], right[k] = t + 2;
    }
 
    vec vals(2 * n);
    for (int_t k = 0; k < n; k++)
        vals[2 * k] = values[k], vals[2 * k + 1] = values[k] + x;
    std::sort(vals.begin(), vals.end());
    std::map<int_t, int_t> compress;    // compressing index
    for (int_t k = 0; k < 2 * n; k++)
        compress[vals[k]] = k;
    int_t max_len = 0;
    vec seg_tree(4 * n, -INF);
    for (int_t k = 0; k < n; k++) {     // k: first index of our suffix
        int_t upper = compress[values[k] + x];
        if (k > 0 && upper > 0) {
            int_t left_len = 0;
            for (int_t a = 0 + 2 * n, b = upper - 1 + 2 * n; a <= b; a /= 2, b /= 2) {
                if (a % 2 == 1)
                    left_len = std::max(left_len, seg_tree[a++]);
                if (b % 2 == 0)
                    left_len = std::max(left_len, seg_tree[b--]);
            }
            max_len = std::max(max_len, left_len + right[k]);
        }
        for (int_t pt = compress[values[k]] + 2 * n; pt > 0; pt /= 2)
            seg_tree[pt] = std::max(seg_tree[pt], left[k]);
    }
    std::cout << max_len << '\n';
}

• 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