Submission #655636

#	Time	Username	Problem	Language	Result	Execution time	Memory
655636		perchuts	Global Warming (CEOI18_glo)	C++17	100 / 100	352 ms	24164 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]);
    }

    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;

        auto p = c.upper_bound(v[i]-x);
        
        if(p==end(c))ckmax(ans, l[i]);
        else ckmax(ans, l[i] + query(n-(*p).second+1));
        

        insert(n-cmp[i]+1, k);
    }

    cout<<ans<<endl;
}

• 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