Submission #14360

#	Time	Username	Problem	Language	Result	Execution time	Memory
14360		Fakeable	정전 (OJUZ10_blackout)	C++98	0 / 100	54 ms	3212 KiB

blackout

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int INF = -2147483648;
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 calc(int x, int y,int limit) {
    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 v1.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], covered);
            iter2 ++;
        }
        else if(iter2 == v2.size()) {
            ans += calc(v1[iter1], v2[iter2-1], covered);
            iter1 ++;
        }
        else {
            ans += calc(v1[iter1], v2[iter2], covered);
            if(v1[iter1] < v2[iter2]) iter1 ++;
            else iter2 ++;
        }
    }
    printf("%d\n",ans);
}
int main() {
    input();
    solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40