Submission #516461

#	Time	Username	Problem	Language	Result	Execution time	Memory
516461		Jomnoi	Global Warming (CEOI18_glo)	C++17	100 / 100	771 ms	54068 KiB

glo

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MX = 2e5 + 10;

int t[MX];
int dp1[MX], dp2[MX];

class SegmentTree {
    protected :
        const int N;
        vector <int> tree;
    public :
        SegmentTree(const int &n) : N(n) {
            tree.resize(4 * N, 0);
        }

        void update(const int &idx, const int &l, const int &r, const int &q, const int &k) {
            if(r < q or q < l) {
                return;
            }
            if(l == r) {
                tree[idx] = max(tree[idx], k);
                return;
            }

            int mid = (l + r) / 2;
            update(idx * 2, l, mid, q, k);
            update(idx * 2 + 1, mid + 1, r, q, k);
            tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
        }

        int query(const int &idx, const int &l, const int &r, const int &ql, const int &qr) {
            if(r < ql or qr < l) {
                return 0;
            }
            if(ql <= l and r <= qr) {
                return tree[idx];
            }

            int mid = (l + r) / 2;
            return max(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
        }
};

int main() {
    int n, x;
    scanf(" %d %d", &n, &x);

    set <int> s;
    unordered_map <int, int> mp;
    for(int i = 1; i <= n; i++) {
        scanf(" %d", &t[i]);
        s.insert(t[i]);
        s.insert(t[i] - x);
    }

    int cnt = 0;
    for(auto v : s) {
        mp[v] = ++cnt;
    }

    SegmentTree st1(cnt), st2(cnt);
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        dp1[i] = st1.query(1, 1, cnt, 1, mp[t[i]] - 1) + 1;
        dp2[i] = st2.query(1, 1, cnt, 1, mp[t[i]] - 1) + 1;
        st1.update(1, 1, cnt, mp[t[i]], dp1[i]);
        st2.update(1, 1, cnt, mp[t[i]], dp2[i]);
        st2.update(1, 1, cnt, mp[t[i] - x], dp1[i]);
        ans = max(ans, max(dp1[i], dp2[i]));
    }
    printf("%d", ans);
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf(" %d %d", &n, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
glo.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf(" %d", &t[i]);
      |         ~~~~~^~~~~~~~~~~~~~

• 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