Submission #655631

#	Time	Username	Problem	Language	Result	Execution time	Memory
655631		perchuts	Global Warming (CEOI18_glo)	C++17	0 / 100	461 ms	24228 KiB

glo

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int cmp[maxn], bit[maxn], l[maxn], n, x;

void insert(int x,int d){
    for(;x<=n;x+=x&(-x))ckmax(bit[x], d);
}

int query(int x){
    int ans = 0;
    while(x){
        ckmax(ans, bit[x]), x -= x&(-x);
    }
    return ans;
}

int main(){_
    //only intervals that matter are [1,i]
    //if we perform the operation on [1,i], we obviously have that v[i] is on the sequence
    //then, size of sequence will be LIS ending at v[i] +  LIS starting at v[j] such that
    //i<j and v[i] - x < v[j]
    //then, precalculate left part and start calculating answer from right, inserting new possible answers in a set.
    cin>>n>>x;

    vector<int>v(n);

    map<int,int>mp, c;

    for(auto&x:v)cin>>x, mp[x] = 1;

    int it = 0;

    for(auto [a,b]:mp)c[a] = ++it;

    for(int i=0;i<n;++i)cmp[i] = c[v[i]];

    for(int i=0;i<n;++i){
        l[i] = query(cmp[i]-1)+1;
        insert(cmp[i], l[i]);
    }

    set<ii>s;

    for(int i=1;i<=n;++i)bit[i] = 0;

    int ans = 0;

    for(int i=n-1;~i;--i){
        int k = query(n-cmp[i]+1)+1;
        insert(n-cmp[i]+1, k);
        auto pt = lower_bound(all(s), make_pair(v[i]-x, inf));
        if(pt!=end(s))ckmax(ans, (*pt).second + l[i]);
        else ckmax(ans, l[i]);
        pt = lower_bound(all(s),make_pair(v[i],0));
        if(pt!=end(s)&&(*pt).second>=k)continue;
        if(pt==end(s)&&pt!=begin(s))pt = prev(pt);
        while(pt!=begin(s)&&(*pt).second<=k)pt = prev(pt), s.erase(next(pt));
        if(pt!=end(s)&&(*pt).second<=k)s.erase(pt);
        s.insert({v[i],k});
    }

    cout<<ans<<endl;
}

• 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