Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include <bits/stdc++.h>
- #include <iostream>
- #include <map>
- #include <set>
- #define mp make_pair
- typedef long long int lli;
- using namespace std;
- int n;
- int a[150005];
- set<int> top;
- set<int> bot;
- set<int> two;
- void findTop()
- {
- for (int i=2 ; i<=n-1 ; i+=2 )
- {
- if ( a[i] <= a[i-1] && a[i] <= a[i+1] )
- top.insert( i );
- }
- }
- void findBot()
- {
- for (int i=3 ; i<=n-1 ; i+=2 )
- {
- if ( a[i] >= a[i-1] && a[i] >= a[i+1] )
- bot.insert( i );
- }
- }
- void findTwo()
- {
- for ( int i=1 ; i<=n-1 ; i+=2 )
- {
- if ( a[i] >= a[i+1] )
- {
- if ( top.find( i+1 ) != top.end() ) continue;
- if ( bot.find( i ) != bot.end() ) continue;
- two.insert( i );
- }
- }
- for ( int i=2 ; i<=n-1 ; i+=2 )
- {
- if ( a[i] <= a[i+1] )
- {
- if ( top.find( i ) != top.end() ) continue;
- if ( bot.find( i+1 ) != bot.end() ) continue;
- two.insert( i );
- }
- }
- }
- lli check( int p , int q )
- {
- int x = a[p] , y = a[q];
- swap( a[p] , a[q] );
- bool f = true;
- if (p%2) f &= (p-1>=1 ? y<a[p-1] : true) && (p+1<=n ? y<a[p+1] : true);
- else f &= (p-1>=1 ? y>a[p-1] : true) && (p+1<=n ? y>a[p+1] : true);
- if (q%2) f &= (q-1>=1 ? x<a[q-1] : true) && (q+1<=n ? x<a[q+1] : true);
- else f &= (q-1>=1 ? x>a[q-1] : true) && (q+1<=n ? x>a[q+1] : true);
- swap( a[p] , a[q] );
- return f ? 1 : 0;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin>>n;
- for (int i=1 ; i<=n ; i++) cin>>a[i];
- findTop(); findBot(); findTwo();
- lli ans = 0;
- // cout<<top.size()<<" "<<bot.size()<<" "<<two.size()<<"\n";
- int ts = top.size() , bs = bot.size() , ws = two.size();
- if ( (top.size() == 1) && (bot.size()+two.size() == 0) )
- {
- int t = *top.begin();
- for (int i=1 ; i<=n ; i++)
- {
- ans += check( i , t );
- }
- }
- else if ( (bot.size() == 1) && (top.size()+two.size() == 0) )
- {
- int t = *bot.begin();
- for (int i=1 ; i<=n ; i++)
- {
- ans += check( i , t );
- }
- }
- else if ( ts==1 && bs==1 && ws==0 )
- {
- int t = *top.begin();
- int b = *bot.begin();
- ans += check( t , b );
- }
- else if ( ts==1 && bs==0 && ws==1 )
- {
- int t = *top.begin();
- int w1 = *two.begin();
- int w2 = w1 + 1;
- ans += check( t , w1 );
- ans += check( t , w2 );
- }
- else if ( ts==0 && bs==1 && ws==1 )
- {
- int b = *bot.begin();
- int w1 = *two.begin();
- int w2 = w1 + 1;
- ans += check( b , w1 );
- ans += check( b , w2 );
- }
- else if ( ts==0 && bs==0 && ws==2 )
- {
- int w1 = *two.begin();
- int w2 = w1 + 1;
- int w3 = *(++two.begin());
- int w4 = w3 + 1;
- ans += check( w1 , w3 );
- ans += check( w1 , w4 );
- ans += check( w2 , w3 );
- ans += check( w2 , w4 );
- }
- else if ( ts==0 && bs==0 && ws==1 )
- {
- int w1 = *two.begin();
- int w2 = w1 + 1;
- for (int i=1 ; i<=n ; i++)
- ans += check( i , w1 );
- for (int i=1 ; i<=n ; i++)
- ans += check( i , w2 );
- ans -= check(w1 , w2);
- }
- cout<<ans<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement