Submission #1271835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271835		win1702	Global Warming (CEOI18_glo)	C++20	10 / 100	90 ms	6716 KiB

glo

// chỉ là khung để bạn build, không phải full chạy ngay
#include <bits/stdc++.h>
using namespace std;
struct BIT {
    int n; vector<int> f;
    BIT(int n): n(n), f(n+1,0){}
    void upd(int i,int v){ for(;i<=n;i+=i&-i) f[i]=max(f[i],v); }
    int get(int i){ int r=0; for(;i>0;i-=i&-i) r=max(r,f[i]); return r; }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; long long x;
    cin>>n>>x;
    vector<long long>a(n);
    for(auto &v:a) cin>>v;

    // compress
    vector<long long> comp=a;
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    auto idx=[&](long long v){
        return int(lower_bound(comp.begin(),comp.end(),v)-comp.begin())+1;
    };

    // LIS_pref
    BIT bit(comp.size());
    vector<int> pref(n);
    for(int i=0;i<n;i++){
        int p = idx(a[i]);
        pref[i] = bit.get(p-1)+1;
        bit.upd(p,pref[i]);
    }

    // LIS_suff (reverse)
    BIT bit2(comp.size());
    vector<int> suff(n);
    for(int i=n-1;i>=0;i--){
        int p = comp.size()-idx(a[i])+1;
        suff[i] = bit2.get(p-1)+1;
        bit2.upd(p,suff[i]);
    }

    // max_left_val[i] = max value on some LIS ending at i
    // min_right_val[i] = min value on some LIS starting at i
    // --> cần truy vấn phức hơn (segment tree + trace)
    // editorial hướng dẫn tính các mảng này.

    // Sau khi có max_left, min_right, duyệt và tính ans
    int ans = *max_element(pref.begin(),pref.end()); // baseline
    // ...
    cout << ans << "\n";
}

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