Zigzag

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <set>

typedef long long LL;

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++){
        int x; cin >> x; v.push_back(x);
    }
    vector<int> up(n), down(n), psv(n), pgv(n);
    up[0] = 1;
    down[0] = 1;
    psv[0] = -1; pgv[0] = -1;
    
    for(int i = 1; i < n; i++){
        if(v[i] == v[i-1]){
            up[i] = up[i-1];
            down[i] = down[i-1];
            psv[i] = psv[i-1];
            pgv[i] = pgv[i-1];
        }
        else if(v[i] > v[i-1]){
            // Increasing
            psv[i] = i-1;
            int prev = pgv[i-1]; // Search for prev greater
            
            while(prev != -1 && v[prev] <= v[i]){
                prev = pgv[prev];
            }
            pgv[i] = prev;
        }
        else if(v[i] < v[i-1]){
            // Decreasing
            pgv[i] = i-1;
            int prev = psv[i-1];
            while(prev != -1 && v[prev] >= v[i]){
                prev = psv[prev];
            }
            psv[i] = prev;
        }
        up[i] = psv[i] == -1 ? 1 : down[psv[i]] + 1;
        down[i] = pgv[i] == -1 ? 1 : up[pgv[i]] + 1;
    }
    /*for(auto x : psv) cout << x << " "; cout << endl;
    for(auto x : pgv) cout << x << " "; cout << endl;
    for(auto x : up) cout << x << " "; cout << endl;
    for(auto x : down) cout << x << " "; cout << endl;*/
    
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans = max(ans,up[i]);
        ans = max(ans,down[i]);
    }
    cout << ans << endl;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: ACCEPTED