oj.uz

Submission #14217

# Submission time Handle Problem Language Result Execution time Memory
14217 2015-05-05T07:35:14 Z khsoo01 정전 (OJUZ10_blackout) C++
0 / 100
 51 ms 4012 KB 
#include<cstdio>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;
int n,l,a[150005],seg[2][150005][2],cnt[2],i,i1,i2,ans;

int main()
{
    scanf("%d%d",&n,&l);
    for(i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    std::sort(a,a+n);
    for(i=0;i<150005;i++){
        seg[0][i][0]=-INF;
        seg[0][i][1]=-INF;
        seg[1][i][0]=-INF;
        seg[1][i][1]=-INF;
    }
    for(i=0;i<n;i+=2) {
        if(seg[0][cnt[0]][1]<a[i]-l+1){
            cnt[0]++;
            seg[0][cnt[0]][0]=a[i]-l+1;
            seg[0][cnt[0]][1]=a[i]+l;
        }
        else seg[0][cnt[0]][1]=a[i]+l;
    }
    for(i=1;i<n;i+=2) {
        if(seg[1][cnt[1]][1]<a[i]-l+1){
            cnt[1]++;
            seg[1][cnt[1]][0]=a[i]-l+1;
            seg[1][cnt[1]][1]=a[i]+l;
        }
        else seg[1][cnt[1]][1]=a[i]+l;
    }
    for(i1=1,i2=1;i1<=cnt[0]&&i2<=cnt[1];) {
        if(seg[0][i1][1]<seg[1][i2][0])i2++;
        else if(seg[1][i2][1]<seg[0][i1][0])i1++;
        else {
            ans+=std::min(seg[0][i1][1],seg[1][i2][1])-std::max(seg[0][i1][0],seg[1][i2][0])+1;
            if(seg[0][i1][1]<seg[1][i2][1])i1++;
            else if(seg[0][i1][1]>seg[1][i2][1])i2++;
            else if(seg[0][i1][0]<seg[1][i2][0])i1++;
            else i2++;
        }
    }
    printf("%d",ans);
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4012 KB Output isn't correct
2 Correct 0 ms 4012 KB Output is correct
3 Incorrect 0 ms 4012 KB Output isn't correct
4 Incorrect 0 ms 4012 KB Output isn't correct
5 Incorrect 1 ms 4012 KB Output isn't correct
6 Incorrect 0 ms 4012 KB Output isn't correct
7 Correct 0 ms 4012 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4012 KB Output is correct
2 Correct 0 ms 4012 KB Output is correct
3 Correct 0 ms 4012 KB Output is correct
4 Correct 2 ms 4012 KB Output is correct
5 Correct 0 ms 4012 KB Output is correct
6 Correct 0 ms 4012 KB Output is correct
7 Incorrect 0 ms 4012 KB Output isn't correct
8 Incorrect 0 ms 4012 KB Output isn't correct
9 Correct 0 ms 4012 KB Output is correct
10 Incorrect 0 ms 4012 KB Output isn't correct

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4012 KB Output isn't correct
2 Incorrect 18 ms 4012 KB Output isn't correct
3 Incorrect 21 ms 4012 KB Output isn't correct
4 Incorrect 51 ms 4012 KB Output isn't correct
5 Incorrect 49 ms 4012 KB Output isn't correct
6 Incorrect 22 ms 4012 KB Output isn't correct
7 Incorrect 26 ms 4012 KB Output isn't correct
8 Incorrect 40 ms 4012 KB Output isn't correct

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 4012 KB Output isn't correct
2 Incorrect 45 ms 4012 KB Output isn't correct
3 Correct 34 ms 4012 KB Output is correct
4 Incorrect 40 ms 4012 KB Output isn't correct
5 Correct 51 ms 4012 KB Output is correct
6 Correct 38 ms 4012 KB Output is correct
7 Incorrect 31 ms 4012 KB Output isn't correct
8 Correct 35 ms 4012 KB Output is correct
9 Incorrect 43 ms 4012 KB Output isn't correct
10 Correct 21 ms 4012 KB Output is correct
11 Incorrect 0 ms 4012 KB Output isn't correct
12 Correct 10 ms 4012 KB Output is correct
13 Incorrect 50 ms 4012 KB Output isn't correct
14 Incorrect 25 ms 4012 KB Output isn't correct
15 Correct 22 ms 4012 KB Output is correct