Submission #1179157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179157		peteza	Global Warming (CEOI18_glo)	C++20	100 / 100	112 ms	10632 KiB

glo

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

int n, x;
int fwk[200005];
int froml[200005], fromr[200005];
tuple<int, int, int> tp[200005], temp[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 mgsort(int l, int r) {
	if(l>=r) return 0;
	int mid = (l+r)>>1;
	int res = max(mgsort(l, mid), mgsort(mid+1, r)); 
	int p1=l, p2=mid+1;
	deque<pair<int, int>> deq;
	for(int i=l;i<=r;i++) {
		if(p1 > mid) temp[i] = tp[p2++];
		else if(p2 > r) {
			while(!deq.empty() && get<0>(tp[p1]) - deq.back().first >= x)
				deq.pop_back();
			if(!deq.empty()) res = max(res, deq.back().second + get<1>(tp[p1]));
			temp[i] = tp[p1++];
		}
		else {
			if(get<0>(tp[p1]) >= get<0>(tp[p2])) {
				while(!deq.empty() && get<2>(tp[p2]) >= deq.front().second) deq.pop_front();
				deq.emplace_front(get<0>(tp[p2]), get<2>(tp[p2]));
				while(!deq.empty() && get<0>(tp[p1]) - deq.back().first >= x)
				deq.pop_back();
				if(!deq.empty()) res = max(res, deq.back().second + get<1>(tp[p1]));
				temp[i] = tp[p2++];
			} else {
				auto rr = upper_bound(deq.rbegin(), deq.rend(), make_pair(get<0>(tp[p1])-x, INT_MAX));
				if(rr!=deq.rend()) res = max(res, rr->second+get<1>(tp[p1]));
				temp[i] = tp[p1++];
			}
		}
	}
	for(int i=l;i<=r;i++) tp[i] = temp[i];
	return res;
}

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(fromr, fromr+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;*/
    for(int i=1;i<=n;i++) tp[i] = {vec[i-1], froml[i], fromr[i]};
    cout << max(cans, mgsort(1, n));
}

• 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