Submission #1084339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084339		serpent_121	Global Warming (CEOI18_glo)	C++17	100 / 100	78 ms	7668 KiB

glo

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <numeric>
#include <cmath>
#include <cstring>
#include <climits>
#include <stack>
#include <bitset>
typedef long long ll;
using namespace std;

const ll MAXN = 2*1e5 + 5;
ll t[MAXN];
int main(){
    ll n,x; cin >> n >> x;
    for ( int i = 0; i<n; i++) cin >> t[i];
    vector<ll> s; ll lis = 0; ll dp[n];
    for (int i = n-1; i>=0; i--) {
        ll l=0; ll r = lis;
        while (l < r) {
            ll mid = (l+r)/2;
            if (s[mid]<=t[i]) r = mid;
            else l = mid+1;
        }
        if (r==lis) {s.push_back(t[i]);lis++;}
        else {
            s[r] = t[i];
        }
        dp[i] = r;
        
    }
    vector<ll> l; lis = 0; ll ans = 0;
    for (int i = 0; i<n; i++) {
        ll pos1 = lower_bound(l.begin(),l.end(),t[i]+x) - l.begin();
        ll pos = lower_bound(l.begin(),l.end(),t[i]) - l.begin();
        ans = max(ans, pos1 + dp[i] + 1);
        if (pos==lis) {
            lis++; l.push_back(t[i]);
        }
        else l[pos] = t[i];
    }
    cout << ans;
}

• 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