# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
215118514 |
Practice:
Kuber |
1467B
- 15
|
C++14 (GCC 6-32)
|
Time limit exceeded on test 2
|
1000 ms
|
4740 KB
|
2023-07-23 05:47:40 |
2023-07-23 05:47:40 |
|
#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define PB push_back
#define MP make_pair
#define FOR for(long long i = 0;i<n;i++)
#define SP << " " <<
#define F first
#define S second
#define MOD 1000000007
#define max_n 200005
#define lMOD 1e16
bool hov(int i, vector<ll> v){
if(i == 0 or i == v.size() - 1) return false;
if(v[i] > v[i-1] and v[i] > v[i+1]) return true;
else if(v[i] < v[i-1] and v[i] < v[i+1]) return true;
else return false;
}
ll calc(int i, vector<ll> v){
ll n;
v[i] = v[i-1];
n = hov(i, v) + hov(i-1, v) + hov(i+1, v);
return n;
}
void solve(){
int n; cin >> n;
vector<ll> a(n);
vector<bool> s(n, false);
ll ans = 0;
for(int i = 0; i< n; i++) {cin >> a[i];
if(i!=0){s[i-1] = hov(i-1, a); ans += s[i-1];}
}
// for(int i = 1; i<n-1; i++){
// if(a[i] > a[i-1] and a[i] > a[i+1]) s[i] = true;
// else if(a[i] < a[i-1] and a[i] < a[i+1]) s[i] = true;
// ans+= s[i];
// }
ll diff = 0;
for(int i = 1 ;i < n-1; i++){
ll old = s[i-1] + s[i] + s[i+1];
ll nu = calc(i, a);
diff = max(diff, old- nu);
}
cout << ans - diff << "\n";
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long t;
// t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Click to see test details