Submission #489829

#	Time	Username	Problem	Language	Result	Execution time	Memory
489829		JovanB	Global Warming (CEOI18_glo)	C++17	100 / 100	355 ms	30200 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;

int dp1[200005];
int dp2[200005];
int niz[200005];
int bit[2000005];

cc_hash_table <int, int> u;

int getmax(int x){
    int res = 0;
    while(x){
        res = max(res, bit[x]);
        x -= x & -x;
    }
    return res;
}

void addbit(int x, int val){
    while(x <= 1000000){
        bit[x] = max(bit[x], val);
        x += x & -x;
    }
}

void clearbit(int n){
    for(int i=1; i<=n; i++) bit[i] = 0; 
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout << fixed;
    
    int n, x;
    cin >> n >> x;
    vector <int> vec;
    for(int i=1; i<=n; i++){
        cin >> niz[i];
        vec.push_back(niz[i]);
        vec.push_back(niz[i] + x);
    }
    sort(vec.begin(), vec.end());
    int cnt = 0;
    for(auto c : vec){
        if(!u[c]) u[c] = ++cnt;
    }
    clearbit(cnt+5);
    for(int i=1; i<=n; i++){
        dp1[i] = 1 + getmax(u[niz[i]] - 1);
        addbit(u[niz[i]], dp1[i]);
    }
    clearbit(cnt+5);
    for(int i=n; i>=1; i--){
        dp2[i] = 1 + getmax(cnt+4-u[niz[i]] - 1);
        addbit(cnt+4-u[niz[i]], dp2[i]);
    }
    clearbit(cnt+5);
    int res = 0;
    for(int i=1; i<=n; i++){
        res = max(res, dp1[i]);
        res = max(res, dp2[i] + getmax(u[niz[i] + x] - 1));
        addbit(u[niz[i]], dp1[i]);
    }
    cout << res << "\n";
    return 0;
}

• 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