Submission #1307771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307771		kevins	Global Warming (CEOI18_glo)	C++20	0 / 100	193 ms	9792 KiB

glo

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

const int MAXN = 200005;
const int INF = 1e9 + 5;

int n, x;
int t[MAXN];
vector<int> vals;

// Binary search for position to insert in LIS arrays
int lis(const vector<int>& a) {
    vector<int> tails;
    for (int val : a) {
        auto it = lower_bound(tails.begin(), tails.end(), val);
        if (it == tails.end()) tails.push_back(val);
        else *it = val;
    }
    return tails.size();
}

// Coordinate compression
int compress(int val) {
    return lower_bound(vals.begin(), vals.end(), val) - vals.begin() + 1;
}

// Fenwick tree for prefix max
struct Fenwick {
    vector<int> bit;
    int n;
    
    Fenwick(int n) : n(n), bit(n + 2, 0) {}
    
    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] = max(bit[idx], val);
    }
    
    int query(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx)
            res = max(res, bit[idx]);
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        vals.push_back(t[i]);
        vals.push_back(t[i] + x);
        if (t[i] > x) vals.push_back(t[i] - x);
    }
    
    // Coordinate compression
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = vals.size();
    
    // Arrays for DP
    vector<int> pref(n + 2, 0), suff(n + 2, 0);
    vector<int> pref_plus(n + 2, 0), suff_plus(n + 2, 0);
    
    // Compute pref[i] = LIS ending at i
    Fenwick fw1(m);
    for (int i = 1; i <= n; i++) {
        int idx = compress(t[i]);
        int lis_ending = fw1.query(idx - 1) + 1;
        pref[i] = lis_ending;
        fw1.update(idx, lis_ending);
    }
    
    // Compute suff[i] = LIS starting at i (by working backwards)
    Fenwick fw2(m);
    for (int i = n; i >= 1; i--) {
        // For decreasing from right, we need to query values greater than current
        // So we compress with reverse ordering
        int idx = compress(t[i]);
        // Query suffix: values > t[i] correspond to indices > idx
        // We can transform by querying total range and subtracting prefix
        int lis_starting = fw2.query(m - idx) + 1;
        suff[i] = lis_starting;
        fw2.update(m - idx + 1, lis_starting);
    }
    
    // Compute pref_plus[i] = LIS ending at i in modified array where 
    // elements from i to n have +x
    Fenwick fw3(m);
    for (int i = 1; i <= n; i++) {
        // Two cases: use original value or value+x for later
        int idx_orig = compress(t[i]);
        int idx_plus = compress(t[i] + x);
        
        // Try extending with original value
        int val1 = fw3.query(idx_orig - 1) + 1;
        // Try extending with +x value (simulating we started +x earlier)
        int val2 = fw3.query(idx_plus - 1) + 1;
        
        pref_plus[i] = max(val1, val2);
        fw3.update(idx_orig, pref_plus[i]);
        fw3.update(idx_plus, pref_plus[i]);
    }
    
    // Compute suff_plus[i] = LIS starting at i in modified array where
    // elements from 1 to i have -x (equivalent to adding x to all except those)
    Fenwick fw4(m);
    for (int i = n; i >= 1; i--) {
        int idx_orig = compress(t[i]);
        int idx_minus = (t[i] > x) ? compress(t[i] - x) : 0;
        
        int val1 = fw4.query(m - idx_orig) + 1;
        int val2 = (idx_minus > 0) ? fw4.query(m - idx_minus) + 1 : 0;
        
        suff_plus[i] = max(val1, val2);
        fw4.update(m - idx_orig + 1, suff_plus[i]);
        if (idx_minus > 0) {
            fw4.update(m - idx_minus + 1, suff_plus[i]);
        }
    }
    
    // Compute answer
    int ans = 0;
    
    // Case 1: no modification
    for (int i = 1; i <= n; i++) {
        ans = max(ans, pref[i] + suff[i] - 1);
    }
    
    // Case 2: modification covers suffix starting at i
    for (int i = 1; i <= n + 1; i++) {
        // elements before i unchanged, from i onward increased by x
        int left = (i > 1) ? pref[i - 1] : 0;
        int right = (i <= n) ? suff_plus[i] : 0;
        ans = max(ans, left + right);
    }
    
    // Case 3: modification covers prefix ending at i
    for (int i = 0; i <= n; i++) {
        // elements up to i increased by x, after i unchanged
        int left = (i >= 1) ? pref_plus[i] : 0;
        int right = (i < n) ? suff[i + 1] : 0;
        ans = max(ans, left + right);
    }
    
    cout << ans << endl;
    
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25