Submission #14362

#TimeUsernameProblemLanguageResultExecution timeMemory
14362Fakeable정전 (OJUZ10_blackout)C++98
0 / 100
48 ms3216 KiB
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int INF = -2100000000;
const int MAX_N = 150500;
int n,l,a[MAX_N],ans,covered = INF;
vector<int> v1,v2;
void input() {
    scanf("%d %d",&n,&l);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);
    return;
}
inline int abs(int x) {
    return x>0?x:-x;
}
inline int calc(int x, int y) {
    if(abs(x-y) >= 2*l) return 0;
    int front, rear;
    if(x<y) {
        rear = x+l;
        front = max(covered, y-l);
        covered = x+l;
    }
    else {
        rear = y+l;
        front = max(covered, x-l);
        covered = y+l;
    }
    return max(rear - front,0);
}
void solve() {
    bool pushzero = true;
    v1.push_back(a[0]);
    for(int i=1;i<n;i++) {
        if(a[i]-a[i-1] < 2*l) {
            if(pushzero) v2.push_back(a[i]), pushzero = false;
            else v1.push_back(a[i]), pushzero = true;
        }
        else v2.push_back(a[i]);
    }
    int iter1 = 0, iter2 = 0;
    while(iter1 < v1.size() || iter2 < v2.size()) {
        //printf("%d %d\n",v1[iter1], v2[iter2]);
        if(iter1 == v1.size()) {
            ans += calc(v1[iter1-1], v2[iter2]);
            iter2 ++;
        }
        else if(iter2 == v2.size()) {
            ans += calc(v1[iter1], v2[iter2-1]);
            iter1 ++;
        }
        else {
            ans += calc(v1[iter1], v2[iter2]);
            if(v1[iter1] < v2[iter2]) iter1 ++;
            else iter2 ++;
        }
    }
    printf("%d\n",ans);
}
int main() {
    input();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...