답안 #954689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954689	2024-03-28T10:58:55 Z	0x34c	Global Warming (CEOI18_glo)	C++17	100 / 100	550 ms	47532 KB

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;

class SegTree {
private:
    vector<int> tree;
    int n;

    int _query(int l, int r, int v, int tl, int tr) {
        if(tr < l || r < tl)
            return 0;
        if(l <= tl && tr <= r)
            return tree[v];
        
        int m = (tl + tr) / 2;
        return max(_query(l, r, 2*v, tl, m), _query(l, r, 2*v + 1, m + 1, tr));
    }

    void _update(int idx, int val, int v, int tl, int tr) {
        if(tl == tr)
            tree[v] = val;
        else {
            int m = (tl + tr) / 2;
            if(idx <= m) _update(idx, val, 2*v, tl, m);
            else _update(idx, val, 2*v + 1, m + 1, tr);
            tree[v] = max(tree[2*v], tree[2*v + 1]);
        }
    }
public:
    SegTree(int N) {
        n = N;
        tree.resize(4*n, 0);
    }
    int query(int l, int r) {
        if(l > r) return 0;
        return _query(l, r, 1, 0, n - 1);
    }
    void update(int idx, int val) {
        return _update(idx, val, 1, 0, n - 1);
    }
};


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int N, X;
    cin >> N >> X;

    vector<int> arr(N);
    map<int, int> cmp;
    set<int> vals;
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
        vals.insert(arr[i]);
    }

    int cmpi = 0;
    for(int i : vals)
        cmp[i] = cmpi++;
    
    // we do the longest decreasing sequence
    SegTree tree(cmpi);
    vector<vector<pii>> sols(cmpi);
    vector<pii> upd(N, {-1, -1});
    for(int i = N - 1; i >= 0; i--) {
        int nxt = cmp[arr[i]] + 1;
        int sol = 1 + tree.query(nxt, cmpi - 1);
        if(sols[nxt - 1].empty() || sols[nxt - 1].back().first < sol) {
            upd[i] = {nxt - 1, sols[nxt - 1].empty() ? 0 : sols[nxt - 1].back().first};
            sols[nxt - 1].push_back({sol, i});
            tree.update(nxt - 1, sol);
        }
    }

    // for(int i = 0; i < cmpi; i++)
    //     cout << tree.query(i, i) << ' ';
    // cout << endl;

    // for(int i = 0; i < N; i++)
    //     cout << "(" << upd[i].first << ", " << upd[i].second << ") ";
    // cout << endl;

    // now we find sol for everything
    vector<int> lis;
    int res = 0;
    for(int i = 0; i < N; i++) {
        if(upd[i].first != -1) {
            tree.update(upd[i].first, upd[i].second);
        }

        // for(int i = 0; i < cmpi; i++)
        //     cout << tree.query(i, i) << ' ';
        // cout << endl;

        int it = arr[i] - X;
        int idx = 0;
        if(lis.empty() || lis.back() < it) {
            lis.push_back(it);
            idx = lis.size() - 1;
        }
        else {
            int l = 0, r = lis.size() - 1;
            int lb = -1;
            while(l <= r) {
                int m = l + (r - l) / 2;
                if(lis[m] >= it) {
                    lb = m;
                    r = m - 1;
                }
                else l = m + 1;
            }

            lis[lb] = it;
            idx = lb;
        }

        // now we find LIS
        auto iter = cmp.upper_bound(it);
        if(iter == cmp.end())
            res = max(res, idx + 1);
        else
            res = max(res, idx + 1 + tree.query(iter->second, cmpi - 1));
    }

    cout << res << endl;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	456 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	456 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	456 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	1 ms	604 KB	Output is correct
21	Correct	1 ms	604 KB	Output is correct
22	Correct	1 ms	856 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	1 ms	604 KB	Output is correct
25	Correct	1 ms	604 KB	Output is correct
26	Correct	1 ms	604 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	461 ms	46028 KB	Output is correct
2	Correct	550 ms	46232 KB	Output is correct
3	Correct	537 ms	46224 KB	Output is correct
4	Correct	485 ms	46164 KB	Output is correct
5	Correct	154 ms	29076 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	11860 KB	Output is correct
2	Correct	76 ms	11860 KB	Output is correct
3	Correct	73 ms	11904 KB	Output is correct
4	Correct	39 ms	7492 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	35 ms	7504 KB	Output is correct
7	Correct	61 ms	11760 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	137 ms	23120 KB	Output is correct
2	Correct	156 ms	23112 KB	Output is correct
3	Correct	361 ms	46224 KB	Output is correct
4	Correct	123 ms	28844 KB	Output is correct
5	Correct	90 ms	23500 KB	Output is correct
6	Correct	162 ms	44204 KB	Output is correct
7	Correct	164 ms	45016 KB	Output is correct
8	Correct	107 ms	23124 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	456 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	1 ms	604 KB	Output is correct
21	Correct	1 ms	604 KB	Output is correct
22	Correct	1 ms	856 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	1 ms	604 KB	Output is correct
25	Correct	1 ms	604 KB	Output is correct
26	Correct	1 ms	604 KB	Output is correct
27	Correct	461 ms	46028 KB	Output is correct
28	Correct	550 ms	46232 KB	Output is correct
29	Correct	537 ms	46224 KB	Output is correct
30	Correct	485 ms	46164 KB	Output is correct
31	Correct	154 ms	29076 KB	Output is correct
32	Correct	76 ms	11860 KB	Output is correct
33	Correct	76 ms	11860 KB	Output is correct
34	Correct	73 ms	11904 KB	Output is correct
35	Correct	39 ms	7492 KB	Output is correct
36	Correct	1 ms	344 KB	Output is correct
37	Correct	35 ms	7504 KB	Output is correct
38	Correct	61 ms	11760 KB	Output is correct
39	Correct	137 ms	23120 KB	Output is correct
40	Correct	156 ms	23112 KB	Output is correct
41	Correct	361 ms	46224 KB	Output is correct
42	Correct	123 ms	28844 KB	Output is correct
43	Correct	90 ms	23500 KB	Output is correct
44	Correct	162 ms	44204 KB	Output is correct
45	Correct	164 ms	45016 KB	Output is correct
46	Correct	107 ms	23124 KB	Output is correct
47	Correct	174 ms	23124 KB	Output is correct
48	Correct	177 ms	23120 KB	Output is correct
49	Correct	501 ms	46092 KB	Output is correct
50	Correct	136 ms	28848 KB	Output is correct
51	Correct	104 ms	25484 KB	Output is correct
52	Correct	216 ms	46580 KB	Output is correct
53	Correct	171 ms	46544 KB	Output is correct
54	Correct	178 ms	47532 KB	Output is correct
55	Correct	288 ms	46164 KB	Output is correct

답안 #954689

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