제출 #1178795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178795		peteza	Global Warming (CEOI18_glo)	C++20	10 / 100	39 ms	5100 KiB

glo

#include <bits/stdc++.h>
using namespace std;

int n, x;
int fwk[200005];
int froml[200005], fromr[200005];

void upd(int x, int val) {
    //cout << x << ' ' << val << '\n';
    for(;x<=200000;x+=x&-x)
        fwk[x] = max(fwk[x], val);
}

int qr(int x) {
    int mx = INT_MIN;
    for(;x;x-=x&-x)
        mx = max(mx, fwk[x]);
    return mx;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> x;
    vector<int> vec(n);
    vector<pair<int, int>> pos(n);
    int i = 0;
    for(auto &e:vec) {
        cin >> e;
        pos[i] = {e, i+1}; i++;
    }
    sort(pos.begin(), pos.end(), [](pair<int, int> a, pair<int, int> b){
        if(a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    });
    for(auto &e:pos) {
        froml[e.second] = qr(e.second) + 1;
        upd(e.second, froml[e.second]);
    } //calc from l
    memset(fwk, 0, sizeof fwk);
    reverse(pos.begin(), pos.end());
    for(auto &e:pos) {
        fromr[e.second] = qr(n-e.second+1) + 1;
        upd(n-e.second+1, fromr[e.second]);
    }
    //for(int i=1;i<=n;i++) cout << fromr[i] << ' ';
    int cans = *max_element(froml, froml+200005);
    if(x == 0) {cout << cans; return 0;}
    //vector<pair<int, int>> vec2;
    set<pair<int, int>> vec2;
    for(int i=n-1;i>=0;i--) {
        if(!vec2.empty()) {
            //auto it = upper_bound(vec2.begin(), vec2.end(), make_pair(vec[i]-x, INT_MAX));
            auto it = vec2.upper_bound(make_pair(vec[i] - x, INT_MAX));
            if(it != vec2.end())
                cans = max(cans, froml[i] + it->second);
        }
        auto toins = make_pair(vec[i], fromr[i]);
        if(vec2.empty() || (--vec2.end())->second <= fromr[i]) {
            while(!vec2.empty() && (--vec2.end())->first >= vec[i]) vec2.erase(--vec2.end());
            vec2.emplace(vec[i], fromr[i]);
        };
    }
    cout << cans;
}

• 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