답안 #417001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417001	2021-06-03T10:08:44 Z	egekabas	Global Warming (CEOI18_glo)	C++14	100 / 100	273 ms	14776 KB

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
struct lis{
    set<pii> s;
    void add(pii nw){
        s.insert(nw);
        auto it = s.lower_bound(nw);
        if(it != s.begin()){
            auto it2 = it;
            --it2;
            if(it2->ss >= it->ss){
                s.erase(it);
                return;
            }
        }
        ++it;
        while(it != s.end()){
            if(it->ss <= nw.ss)
                it = s.erase(it);
            else
                break;
        }
    }
    ll get(ll x){
        auto it = s.lower_bound({x, 0});
        if(it == s.begin())
            return 0;
        --it;
        return it->ss;    
    }
};
lis s1, s2;
ll n, x;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> x;
    ll ans = 0;
    while(n--){
        ll a;
        cin >> a;
        
        ll val = max(s1.get(a+x), s2.get(a));
        ans = max(ans, val+1);
        s2.add({a, val+1});

        
        val = s1.get(a);
        ans = max(ans, val+1);
        s1.add({a, val+1});

        
    }
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	308 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	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	308 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 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	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	308 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	320 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	348 KB	Output is correct
2	Correct	163 ms	348 KB	Output is correct
3	Correct	163 ms	344 KB	Output is correct
4	Correct	170 ms	372 KB	Output is correct
5	Correct	204 ms	12732 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	332 KB	Output is correct
2	Correct	38 ms	716 KB	Output is correct
3	Correct	38 ms	840 KB	Output is correct
4	Correct	44 ms	3688 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	60 ms	3648 KB	Output is correct
7	Correct	30 ms	832 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	328 KB	Output is correct
2	Correct	73 ms	344 KB	Output is correct
3	Correct	154 ms	360 KB	Output is correct
4	Correct	142 ms	8572 KB	Output is correct
5	Correct	130 ms	6496 KB	Output is correct
6	Correct	193 ms	12100 KB	Output is correct
7	Correct	160 ms	12076 KB	Output is correct
8	Correct	58 ms	332 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	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	308 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	320 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	164 ms	348 KB	Output is correct
28	Correct	163 ms	348 KB	Output is correct
29	Correct	163 ms	344 KB	Output is correct
30	Correct	170 ms	372 KB	Output is correct
31	Correct	204 ms	12732 KB	Output is correct
32	Correct	38 ms	332 KB	Output is correct
33	Correct	38 ms	716 KB	Output is correct
34	Correct	38 ms	840 KB	Output is correct
35	Correct	44 ms	3688 KB	Output is correct
36	Correct	1 ms	204 KB	Output is correct
37	Correct	60 ms	3648 KB	Output is correct
38	Correct	30 ms	832 KB	Output is correct
39	Correct	73 ms	328 KB	Output is correct
40	Correct	73 ms	344 KB	Output is correct
41	Correct	154 ms	360 KB	Output is correct
42	Correct	142 ms	8572 KB	Output is correct
43	Correct	130 ms	6496 KB	Output is correct
44	Correct	193 ms	12100 KB	Output is correct
45	Correct	160 ms	12076 KB	Output is correct
46	Correct	58 ms	332 KB	Output is correct
47	Correct	78 ms	1216 KB	Output is correct
48	Correct	79 ms	1224 KB	Output is correct
49	Correct	167 ms	2324 KB	Output is correct
50	Correct	203 ms	13896 KB	Output is correct
51	Correct	201 ms	13640 KB	Output is correct
52	Correct	273 ms	14028 KB	Output is correct
53	Correct	208 ms	14148 KB	Output is correct
54	Correct	169 ms	14776 KB	Output is correct
55	Correct	135 ms	2260 KB	Output is correct

답안 #417001

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