玄关求调
查看原帖
玄关求调
1353331
__qp__楼主2024/8/4 20:50
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 1e7;
bool cmp(int &a, int &b){
	if(a < b){
		a = b;
		return true;
	}
	return false;
}
int n, m;
int* t = new int[MAXN];  
pair<int, int>* a = new pair<int, int>[MAXN];
signed main(){
    cin >> n >> m;
    int e = 0;  
    for(int i = 1;i <= n;i++){
        cin >> t[i];
        a[e++] = {t[i], 1};
        a[e++] = {t[i] + m, -1};
    }
    sort(t, t + n);
	for(int i = 1;i <= n;i++){
    	a[e++] = {t[i], -1};
    	a[e++] = {t[i], 1};
    	a[e++] = {t[i] + m, -1};
    	a[e++] = {t[i] + m, 1};
	}
    sort(a, a + e);
    int cnt[2] = {0};
    int ans = 0, tot = 0;
    int l = 0, r = 0, ll = 0, rr = 0;
    for(int i = 1;i <= n;i++){
        while(l < e && (a[l].first < t[i] || (a[l].first == t[i] && a[l].second == -1))){
            if(l > 0){
                int len = a[l].first - a[l - 1].first;
                if(ll == 1) cnt[0] -= len;
                if(ll == 2) cnt[1] -= len;
            }
            ll += a[l].second;
            l++;
        }
        while(r < e && (a[r].first < t[i] + m || (a[r].first == t[i] + m && a[r].second == -1))){
            if(r > 0){
                int len = a[r].first - a[r - 1].first;
                if(rr == 1){
                    cnt[0] += len;
                    tot += len;
                }
                if(rr == 2){
                    cnt[1] += len;
                }
            }
            rr += a[r].second;
            r++;
        }
  		int q = cnt[1] - cnt[0];
        cmp(ans, q);
	}
    int czsb = ans + m + tot;
    cout << czsb << '\n';
    return 0;
}

90pts90pts

2024/8/4 20:50
加载中...