# Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov! need help in Problem B

Why is my code here is showing runtime error, I checked it thoroughly. Can anyone suggest any improvement.
Any sorts of debugging or other way to solve this problem is appreciated.

Question link: - Problem - B - Codeforces

My Solution : -
#include
#include<bits/stdc++.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include
#define wl int t;cin>>t;while(t–)
#define l long
#define ll long long
#define ul unsigned long
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
const unsigned int m= 1000000007;

``````    int main()
{
fast
wl
{
int n,k;
cin>>n>>k;

int a[n];
for(int p=0;p<n;p++)
cin>>a[p];

int s = n-k;
int max =0, le=0,j,i;
for( i= 0; i<=s; i++)
{
int c=0;
for( j=i+1;j<=j+k-3;j++)
{
if(a[j]>a[j-1] && a[j]>a[j+1])
c++;

}

if(c>max)
{
max = c;
le = i+1;
}

}

cout<<max+1<<" "<<le<<endl;

}
return 0;
}
``````

I think you might get TLE with this approach…what verdict did you get when you submitted it ?

1 Like

There are many errors. You have used wrong condition in second for loop (j<=j+k-3). Even if you correct it, this will give TLE as 3≤k≤n≤2⋅10^5. Your comp is O(k*n).
You can see the solution of other people or wait for editorial.

1 Like

#include <bits/stdc++.h>
using namespace std;

#define lld long long int

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lld t;
cin>>t;
while(t–)
{
lld n,k,i;
cin>>n>>k;
lld arr[n+1];
for(int i=1;i<=n;i++)
cin>>arr[i];
int peaks=0,res=1;
unordered_set s;
for(i=2;i<k;i++)
{
if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
{
peaks++;
s.insert(i);
}
}
int start=2;
for(i=k;i<n;i++)
{
if(s.find(start)!=s.end())
s.erase(s.find(start));
if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
{
s.insert(i);
//cout<<i<<" “<<s.size()<<” in\n";
}
if(peaks<s.size())
{
peaks=s.size();
res=start;
//cout<<peaks<<" “<<start<<”\n";
}
start++;
}
//cout<<"\n";
cout<<peaks+1<<" “<<res<<”\n";
}
}

1 Like

I got RE.

Thank you so much @sebastian I got my mistake…appreciate it brother Your welcome don’t you think this line doesn’t make any sense instead use for( j=i+1;j<i+k-1;j++). Moreover still it will give tle so use prefix sum and for help you may check my submission Submission #77818057 - Codeforces

1 Like

I don’t understand why you need 2 loops, but here’s what I did:

I took an array peak[i] which tells if index i is peak or not.

decrement k twice, so you don’t have to worry about the boundary peak condition.

Now, use a sliding window of length k, and keep updating the answer, when you find, total peaks in sliding window is more than max_so_far.

Here’s the code:

1 Like

I got it… thanks  