Submission #534554

#	Time	Username	Problem	Language	Result	Execution time	Memory
534554		Saeed_247	Global Warming (CEOI18_glo)	C++17	100 / 100	1402 ms	148708 KiB

glo

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

class Node {
    int left; // Left boundary of the current SegmentTree node
    int right; // Right boundary of the current SegmentTree node
    long long mx = 0, lazy = 0;
    Node* right_child;
    Node* left_child;
    public:
    Node(int l, int r) {
        left = l;
        right = r;
        if (l == r) { // Leaf
            ;
        } else { // Construct children
            int m = (l + r) / 2;
            left_child = new Node(l, m);
            right_child = new Node(m + 1, r);

            // Update accumulated result
            mx = max(left_child->mx, right_child->mx);
        }
    }

    void update(int l, int r, long long X) {
        // Lazy propagation
        propagate();
        if ((r < left) || (right < l)) {
            // If updated interval doesn't overlap with current subtree
            return;
        } else if ((l <= left) && (right <= r)) {
            lazy = max(lazy, X);
            
            // Lazy propagation
            propagate();
        } else {
            // If updated interval partially overlaps with current subtree
            left_child->update(l, r, X);
            right_child->update(l, r, X);
            // Update accumulated result
            mx = max(left_child->mx, right_child->mx);
        }
    }

    long long int query(int l, int r) {
        // Lazy propagation
        propagate();
        if ((r < left) || (right < l)) {
            // If requested interval doesn't overlap with current subtree
            return LLONG_MIN;
        } else if ((l <= left) && (right <= r)) {
            // If requested interval fully covers the current subtree
            return mx;
        } else {
            // If requested interval partially overlaps with current subtree
            return max(left_child->query(l, r), right_child->query(l, r));
        }
    }

    void propagate() {
        
        //add to sum
        mx = max(mx, lazy);
        if (right != left) { // Current node is not a leaf
            //update childs lazy
            left_child->lazy = max(left_child->lazy, lazy);
            right_child->lazy = max(right_child->lazy, lazy);
        }
        // Reset
        lazy = 0;
    }
};

const int N = 2e5 + 10;
long long n, x, arr[N], dp[2][N];
vector<long long> comp;
unordered_map<long long, int> mp;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        comp.push_back(arr[i] - x), comp.push_back(arr[i]), comp.push_back(arr[i] + x);
    }
    comp.push_back(-1e18);
    comp.push_back(1e18);
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    Node seg1(0, comp.size()), seg2(0, comp.size());
    for (int i = 0; i < comp.size(); i++) {
        mp[comp[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        int a = mp[arr[i]], b = mp[arr[i] + x];
        dp[0][i] = seg1.query(0, a - 1) + 1;
        dp[1][i] = max(seg2.query(0, a -1), seg1.query(0, b - 1)) + 1;
        seg1.update(a, a, dp[0][i]);
        seg2.update(a, a, dp[1][i]);
    }
    long long mx = 0;
    for (int i = 0; i < 2; i++) for (int j = 0; j <= n; j++) mx = max(mx, dp[i][j]);
    cout << mx << '\n';
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < comp.size(); 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