Submission #1277948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277948		zagaro	Global Warming (CEOI18_glo)	C++20	100 / 100	556 ms	9428 KiB

glo

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
vector<ll> vec;
vector<ll> vic;
void act(ll ind, ll l, ll r, ll x, ll y, ll val){
    if(y<l || x>r)return ;
    if(l == r){vec[l] = min(val, vec[l]);return ;}
    if(x <= l && r <= y){vic[ind] = min(vic[ind], val);return ;}
    if(vic[ind] != LONG_LONG_MAX){
        act(ind*2, l, (l+r)/2,  l, (l+r)/2, vic[ind]);
        act(ind*2+1, (l+r)/2+1, r,  (l+r)/2+1, r, vic[ind]);
        vic[ind] = LONG_LONG_MAX;
    }
    act(ind*2, l, (l+r)/2,  x, y, val);
    act(ind*2+1, (l+r)/2+1, r,  x, y, val);
    return ;
}
ll fnd(ll ind, ll l, ll r, ll x){
    if(x < l || x > r)return LONG_LONG_MAX;
    if(l == r)return vec[l];
    if(vic[ind] != LONG_LONG_MAX){
        act(ind*2, l, (l+r)/2,  l, (l+r)/2, vic[ind]);
        act(ind*2+1, (l+r)/2+1, r,  (l+r)/2+1, r, vic[ind]);
        vic[ind] = LONG_LONG_MAX;
    }
    return min(fnd(ind*2, l, (l+r)/2, x), fnd(ind*2+1, (l+r)/2+1, r, x));
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, d, x, l, r, m, R=0, p;
    cin>>n>>d;
    vector<ll> dp(1, 0);
    vec.assign(n+2, LONG_LONG_MAX);
    vic.assign(4*(n+1)+1, LONG_LONG_MAX);
    for(int i=1;i<=n;i++){
        cin>>x;
        l=0;r=R+1;
        wl(l<r-1){
            m = (l+r)/2;
            if(fnd(1, 1, n, m) >= x+d)r=m;
            else l=m;
        }
        p=r;
        l=0;r=dp.size();
        wl(l<r-1){
            m = (l+r)/2;
            if(dp[m] >= x+d)r=m;
            else l=m;
        }
        p = max(p, r);
        R = max(R, p);
        act(1, 1, n, 1, p, x+d);
        l=0;r=dp.size();
        wl(l<r-1){
            m = (l+r)/2;
            if(dp[m] >= x)r=m;
            else l=m;
        }
        if(r == dp.size())dp.push_back(x);
        else dp[r] = x;
    }
    R = max(R, ll(dp.size()-1));
    cout<<R<<ENDL;
    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