-
Notifications
You must be signed in to change notification settings - Fork 0
/
hacker rank street light
46 lines (40 loc) · 1.15 KB
/
hacker rank street light
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, q;
cin>>q>>n;
//use a scanline algorithm
// Dark -- if element is --- a : zero, b: a[i] > 0
//light ---if element is 1 i.e a[i] == 1 means light
int a[n + 1] = {0};// marks all the elements are dark(a[i] is 0)
//performe quries
for(int i = 0 ; i < q; i++){
int l, r;
cin>>l>>r;
//use a sanline algorithm
if( l - r >= 0)
a[l -r]++; //a[l -r] += 1;
else
a[0]++; // a[0] += 1;
if(l + r + 1 <= n){
a[l + r + 1]--; // a[l + r] -= 1;
}
}
//find a prefix sum
for(int i = 1; i<=n; i++)
a[i] +=a[i -1];
int cnt , res = -9999999;
//traverse every elements of array if a[i]>=0 then count i.e we find a dark
//if a[i] == 1 i.e light
for(int i= 0; i <= n; i++){
cnt = 0;
//if a[i] >=0 and a[i] is not equal to 1 then count++
while( a[i] != 1 && i<= n){
i++;
cnt++;
}
//store a max continious dark
res = max(res , cnt);
}
cout<<res<<endl;
}