Zigzag

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <unordered_set>
#include <stdio.h>
#include <string.h>
#include <unordered_map>
#include <fstream>
#include <set>
#include <map>

#define MOD 1000000007
#define ll long long
#define N (1<<17)
#define float double

using namespace std;

int nytA[2*N];
int nytY[2*N];

void set_val(int i, int val, int *spuu){
    i+=N;
    spuu[i]=val;
    i/=2;
    while(i){
        spuu[i]=max(spuu[2*i],spuu[2*i+1]);
        i/=2;
    }
}

int query_max(int l, int r, int* spuu){
    int v=0;
    l+=N;r+=N;

    while(l<r){
        if(l%2==1){
            v=max(v,spuu[l]);
            l++;
        }
        if(r%2==0){
            v=max(v,spuu[r]);
            r--;
        }
        r/=2;l/=2;
    }
    if(l==r)
        v=max(v,spuu[l]);
    return v;
}

int m_pre[100000];
int m_cp[100000];
int m[100000];

int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>m_pre[i];
    for(int i=0; i<n; i++)
        m_cp[i]=m_pre[i];
    sort(m_pre,m_pre+n);
    unordered_map<int,int> comp;
    int temp=0;
    comp[m_pre[0]]=temp;
    for(int i=1; i<n; i++){
        if(m_pre[i]!=m_pre[i+1]){
            temp++;
            comp[m_pre[i]]=temp;
        }
    }

    for(int i=0; i<n; i++)
        m[i]=comp[m_cp[i]];

    int vast=0;
    for(int i=0; i<n; i++){
        int yl=query_max(0,m[i]-1,nytA) + 1;
        int al=query_max(m[i]+1,100001,nytY)+1;
        vast=max(vast,max(yl,al));
        set_val(m[i], yl, nytY);
        set_val(m[i], al, nytA);
    }

    cout<<vast<<endl;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED