Submission #13936

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13936	2015-04-24T05:20:09 Z	model_code	정전 (OJUZ10_blackout)	C++	100 / 100	71 ms	3428 KB

blackout

#include<stdio.h>
#include<algorithm>
using namespace std;

struct intv {
	int x, ad;
	bool operator< (const intv& c) const {
		if(x != c.x)return x<c.x;
		return ad<c.ad;
	}
}ba[300300];

int n, l, t;
long long sum;

int main(){
	int i, a, pv;
	scanf("%d%d", &n, &l);
	for(i=0; i<n; i++){
		scanf("%d", &a);
		ba[2*i].x=a-l, ba[2*i].ad=1;
		ba[2*i+1].x=a+l, ba[2*i+1].ad=-1;
	}
	sort(ba, ba+2*n);
	for(i=0; i<2*n; i++){
		if(i>0 && t>=2)sum+=ba[i].x-ba[i-1].x;
		t+=ba[i].ad;
	}
	printf("%lld", sum);
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3428 KB	Output is correct
2	Correct	0 ms	3428 KB	Output is correct
3	Correct	0 ms	3428 KB	Output is correct
4	Correct	0 ms	3428 KB	Output is correct
5	Correct	0 ms	3428 KB	Output is correct
6	Correct	0 ms	3428 KB	Output is correct
7	Correct	0 ms	3428 KB	Output is correct

Subtask #2

20.0 / 20.0

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

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3428 KB	Output is correct
2	Correct	63 ms	3428 KB	Output is correct
3	Correct	70 ms	3428 KB	Output is correct
4	Correct	45 ms	3428 KB	Output is correct
5	Correct	22 ms	3428 KB	Output is correct
6	Correct	37 ms	3428 KB	Output is correct
7	Correct	26 ms	3428 KB	Output is correct
8	Correct	67 ms	3428 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	3428 KB	Output is correct
2	Correct	71 ms	3428 KB	Output is correct
3	Correct	44 ms	3428 KB	Output is correct
4	Correct	37 ms	3428 KB	Output is correct
5	Correct	0 ms	3428 KB	Output is correct
6	Correct	27 ms	3428 KB	Output is correct
7	Correct	63 ms	3428 KB	Output is correct
8	Correct	47 ms	3428 KB	Output is correct
9	Correct	61 ms	3428 KB	Output is correct
10	Correct	45 ms	3428 KB	Output is correct
11	Correct	47 ms	3428 KB	Output is correct
12	Correct	64 ms	3428 KB	Output is correct
13	Correct	56 ms	3428 KB	Output is correct
14	Correct	59 ms	3428 KB	Output is correct
15	Correct	46 ms	3428 KB	Output is correct