Submission #19103

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
19103	2016-02-18 11:01:32	Namnamseo	정전 (OJUZ10_blackout)	C++14	100 / 100	69 ms	4012 KiB

blackout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> pp;
int p[150010];
pp query[300010];
int n,l;
int main()
{
    scanf("%d%d",&n,&l);
    int i;
    for(i=0;i<n;++i) scanf("%d",p+i);
    sort(p,p+n);
    for(i=0;i<n;++i){
        query[i*2]={p[i]-l,i%2+1};
        query[i*2+1]={p[i]+l,-(i%2+1)};
    }
    sort(query, query+2*n);
    unsigned int ans=0;
    int last=0;
    int on[3]={0,0,0};
    for(i=0;i<2*n;++i){
        pp& cq=query[i];
        if(on[1] && on[2]){
            ans+=((unsigned)(cq.first))-last;
        }
        if(cq.second>0) ++on[cq.second];
        else --on[-cq.second];
        last=cq.first;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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