oj.uz

Submission #622276

# Submission time Handle Problem Language Result Execution time Memory
622276 2022-08-04T05:45:58 Z jophyyjh Global Warming (CEOI18_glo) C++14
100 / 100
 647 ms 43072 KB 
/**
 * 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.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 476 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 30412 KB Output is correct
2 Correct 401 ms 30532 KB Output is correct
3 Correct 369 ms 30440 KB Output is correct
4 Correct 402 ms 30368 KB Output is correct
5 Correct 162 ms 23364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10932 KB Output is correct
2 Correct 79 ms 10984 KB Output is correct
3 Correct 78 ms 10932 KB Output is correct
4 Correct 37 ms 7664 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 38 ms 7660 KB Output is correct
7 Correct 55 ms 9944 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 21704 KB Output is correct
2 Correct 266 ms 21652 KB Output is correct
3 Correct 647 ms 42868 KB Output is correct
4 Correct 196 ms 29556 KB Output is correct
5 Correct 130 ms 21260 KB Output is correct
6 Correct 219 ms 40132 KB Output is correct
7 Correct 229 ms 40872 KB Output is correct
8 Correct 166 ms 21660 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 476 KB Output is correct
27 Correct 379 ms 30412 KB Output is correct
28 Correct 401 ms 30532 KB Output is correct
29 Correct 369 ms 30440 KB Output is correct
30 Correct 402 ms 30368 KB Output is correct
31 Correct 162 ms 23364 KB Output is correct
32 Correct 72 ms 10932 KB Output is correct
33 Correct 79 ms 10984 KB Output is correct
34 Correct 78 ms 10932 KB Output is correct
35 Correct 37 ms 7664 KB Output is correct
36 Correct 1 ms 320 KB Output is correct
37 Correct 38 ms 7660 KB Output is correct
38 Correct 55 ms 9944 KB Output is correct
39 Correct 256 ms 21704 KB Output is correct
40 Correct 266 ms 21652 KB Output is correct
41 Correct 647 ms 42868 KB Output is correct
42 Correct 196 ms 29556 KB Output is correct
43 Correct 130 ms 21260 KB Output is correct
44 Correct 219 ms 40132 KB Output is correct
45 Correct 229 ms 40872 KB Output is correct
46 Correct 166 ms 21660 KB Output is correct
47 Correct 214 ms 21652 KB Output is correct
48 Correct 187 ms 21648 KB Output is correct
49 Correct 502 ms 42956 KB Output is correct
50 Correct 173 ms 29624 KB Output is correct
51 Correct 153 ms 22312 KB Output is correct
52 Correct 231 ms 29772 KB Output is correct
53 Correct 246 ms 42300 KB Output is correct
54 Correct 253 ms 43072 KB Output is correct
55 Correct 315 ms 38748 KB Output is correct