답안 #501006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501006	2022-01-02T04:23:53 Z	blue	Global Warming (CEOI18_glo)	C++17	100 / 100	179 ms	6372 KB

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*

Obs 1. If the temperature is increased, then it is optimal to increase the temperature of an interval containing
       a suffix of the LIS.

Obs 2. The temperatures should be increased for a suffix of the given array, by +x.

*/
int n, x;
int t[200001];

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> t[i];

    int I[2*n];
    for(int i = 0; i < n; i++)
    {
        I[i] = i+1;
        I[i+n] = -i-1;
    }

    sort(I, I + 2*n, [] (int p, int q)
    {
        int a1 = (p > 0 ? t[p] : t[-p] + x);
        int a2 = (q > 0 ? t[q] : t[-q] + x);

        if(a1 == a2) return abs(p) > abs(q);    // if specific test cases fail, check this part.
        return a1 < a2;
    });

    vector<int> lis0(n+1, 0), lis1(n+1, 0); //before increase, after increase

    int res = 0;

    for(int i:I)
    {

        // cout << i << ' ';
        if(i > 0)
        {
            for(int j = i-1; j >= 1; j -= j&-j) lis0[i] = max(lis0[i], lis0[j]);
            lis0[i]++;

            res = max(res, lis0[i]);

            for(int j = i; j <= n; j += j&-j) lis0[j] = max(lis0[j], lis0[i]);

        }
        else
        {
            for(int j = -i-1; j >= 1; j -= j&-j) lis1[-i] = max(lis1[-i], max(lis0[j], lis1[j]));
            lis1[-i]++;

            res = max(res, lis1[-i]);

            for(int j = -i; j <= n; j += j&-j) lis1[j] = max(lis1[j], lis1[-i]);
        }
    }
    // cout << '\n';

    cout << res << '\n';
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	280 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	280 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	308 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	300 KB	Output is correct
18	Correct	0 ms	296 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	280 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	308 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	300 KB	Output is correct
18	Correct	0 ms	296 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	304 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	288 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	308 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	165 ms	6052 KB	Output is correct
2	Correct	175 ms	6216 KB	Output is correct
3	Correct	168 ms	6084 KB	Output is correct
4	Correct	168 ms	6076 KB	Output is correct
5	Correct	113 ms	5348 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	1636 KB	Output is correct
2	Correct	38 ms	1732 KB	Output is correct
3	Correct	38 ms	1652 KB	Output is correct
4	Correct	24 ms	1460 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	30 ms	1460 KB	Output is correct
7	Correct	36 ms	1712 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	3156 KB	Output is correct
2	Correct	63 ms	3136 KB	Output is correct
3	Correct	144 ms	6088 KB	Output is correct
4	Correct	94 ms	5444 KB	Output is correct
5	Correct	38 ms	2756 KB	Output is correct
6	Correct	83 ms	5140 KB	Output is correct
7	Correct	101 ms	5764 KB	Output is correct
8	Correct	61 ms	3232 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	280 KB	Output is correct
3	Correct	0 ms	308 KB	Output is correct
4	Correct	0 ms	308 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	308 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	300 KB	Output is correct
18	Correct	0 ms	296 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	304 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	288 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	308 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	165 ms	6052 KB	Output is correct
28	Correct	175 ms	6216 KB	Output is correct
29	Correct	168 ms	6084 KB	Output is correct
30	Correct	168 ms	6076 KB	Output is correct
31	Correct	113 ms	5348 KB	Output is correct
32	Correct	37 ms	1636 KB	Output is correct
33	Correct	38 ms	1732 KB	Output is correct
34	Correct	38 ms	1652 KB	Output is correct
35	Correct	24 ms	1460 KB	Output is correct
36	Correct	0 ms	204 KB	Output is correct
37	Correct	30 ms	1460 KB	Output is correct
38	Correct	36 ms	1712 KB	Output is correct
39	Correct	62 ms	3156 KB	Output is correct
40	Correct	63 ms	3136 KB	Output is correct
41	Correct	144 ms	6088 KB	Output is correct
42	Correct	94 ms	5444 KB	Output is correct
43	Correct	38 ms	2756 KB	Output is correct
44	Correct	83 ms	5140 KB	Output is correct
45	Correct	101 ms	5764 KB	Output is correct
46	Correct	61 ms	3232 KB	Output is correct
47	Correct	80 ms	3120 KB	Output is correct
48	Correct	79 ms	3152 KB	Output is correct
49	Correct	179 ms	6372 KB	Output is correct
50	Correct	99 ms	5328 KB	Output is correct
51	Correct	78 ms	4048 KB	Output is correct
52	Correct	112 ms	5420 KB	Output is correct
53	Correct	87 ms	5384 KB	Output is correct
54	Correct	108 ms	6084 KB	Output is correct
55	Correct	161 ms	6116 KB	Output is correct

답안 #501006

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0