Submission #1226798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226798		yassia	Global Warming (CEOI18_glo)	C++20	48 / 100	1058 ms	320644 KiB

glo

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);

struct sg {
    ll ans = 0;
    sg *l = nullptr, *r = nullptr;
    sg(){
        ans = 0;
        l = nullptr;
        r =nullptr;
    }
    void update(ll left, ll right, ll ix, ll val){
        if (ix < left || right<=ix) {
            return;
        }
        else if (ix == left && ix+1==right) {
            ans =val;
            return;
        }
        else {
            ll mid = (left + right)/2;
            if (!l) l = new sg(); l->update(left, mid, ix, val);
            if (!r) r = new sg(); r->update(mid, right, ix,val);
            ans = max(l->ans, r->ans);
        }
    }
    ll get(ll left, ll right, ll sl, ll sr) {
        if (right <= sl || left >= sr) {
            return 0;
        }
        else if (sl <= left && right <= sr) {
            return ans;
        }
        else {
            ll mid = (left + right)/2;
            ll ansl = 0; ll ansr = 0;
            if (l) ansl = l->get(left, mid, sl, sr);
            if (r) ansr = r->get(mid, right, sl, sr);
            return max(ansl,ansr);
        }
    }
};

sg d1 = sg();
sg d2 = sg();
vector<vector<ll>> changes;
ll dp[200005];
ll dp1[200005];
void solve1() {
    ll n, x;
    cin >> n >> x;
    vector<ll> t(n);
    ll maxA = x;
    for (int i =0; i <n ;i++){
        cin>>t[i];
        maxA= max(maxA, t[i]);
    }
    ll cnt= maxA;

    ll mx = 0;
    for (int i = n-1; i >=0; i--){
        dp[i] = d1.get(0, cnt+1, t[i]+1, cnt+1)+1;
        mx =max(mx, dp[i]);
        changes.push_back({t[i], d1.get( 0, cnt+1, t[i], t[i]+1)});
        if (changes.back()[1] < dp[i]) {
            d1.update(0, cnt+1, t[i], dp[i]);
        }
    }
    for (int i =0; i < n; i++){
        d1.update(0, cnt+1, changes.back()[0],changes.back()[1]);
        dp1[i] = d2.get(0, cnt+1, 0, t[i])+1;
        if (d2.get(0, cnt+1, t[i] ,t[i]+1)< dp1[i]){
            d2.update(0, cnt+1, t[i], dp1[i]);
        }
        mx= max(mx, dp1[i]);
        mx = max(mx, dp1[i] + d1.get(0, cnt+1, max(0ll, t[i]-x+1), cnt+1));
        changes.pop_back();
    }
    cout<<mx;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ll t1 = 1;
    for (int _ = 0; _ < t1; ++_) solve1();
#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25