Guest User

Untitled

a guest
Mar 19th, 2016
270
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. //#include <bits/stdc++.h>
  3. #include <iostream>
  4. #include <map>
  5. #include <set>
  6. #define mp make_pair
  7. typedef long long int lli;
  8. using namespace std;
  9.  
  10. int n;
  11. int a[150005];
  12. set<int> top;
  13. set<int> bot;
  14. set<int> two;
  15.  
  16. void findTop()
  17. {
  18.     for (int i=2 ; i<=n-1 ; i+=2 )
  19.     {
  20.         if ( a[i] <= a[i-1] && a[i] <= a[i+1] )
  21.             top.insert( i );
  22.     }
  23. }
  24.  
  25. void findBot()
  26. {
  27.     for (int i=3 ; i<=n-1 ; i+=2 )
  28.     {
  29.         if ( a[i] >= a[i-1] && a[i] >= a[i+1] )
  30.             bot.insert( i );
  31.     }
  32. }
  33.  
  34. void findTwo()
  35. {
  36.     for ( int i=1 ; i<=n-1 ; i+=2 )
  37.     {
  38.         if ( a[i] >= a[i+1] )
  39.         {
  40.             if ( top.find( i+1 ) != top.end() ) continue;
  41.             if ( bot.find( i ) != bot.end() ) continue;
  42.             two.insert( i );
  43.         }
  44.     }
  45.    
  46.     for ( int i=2 ; i<=n-1 ; i+=2 )
  47.     {
  48.         if ( a[i] <= a[i+1] )
  49.         {
  50.             if ( top.find( i ) != top.end() ) continue;
  51.             if ( bot.find( i+1 ) != bot.end() ) continue;
  52.             two.insert( i );
  53.         }
  54.     }
  55. }
  56.  
  57. lli check( int p , int q )
  58. {
  59.     int x = a[p] , y = a[q];
  60.     swap( a[p] , a[q] );
  61.     bool f = true;
  62.    
  63.     if (p%2) f &= (p-1>=1 ? y<a[p-1] : true) && (p+1<=n ? y<a[p+1] : true);
  64.     else     f &= (p-1>=1 ? y>a[p-1] : true) && (p+1<=n ? y>a[p+1] : true);
  65.    
  66.     if (q%2) f &= (q-1>=1 ? x<a[q-1] : true) && (q+1<=n ? x<a[q+1] : true);
  67.     else     f &= (q-1>=1 ? x>a[q-1] : true) && (q+1<=n ? x>a[q+1] : true);
  68.    
  69.     swap( a[p] , a[q] );
  70.     return f ? 1 : 0;
  71. }
  72.  
  73. int main()
  74. {
  75.     ios_base::sync_with_stdio(false);
  76.    
  77.     cin>>n;
  78.    
  79.     for (int i=1 ; i<=n ; i++) cin>>a[i];
  80.     findTop(); findBot(); findTwo();
  81.    
  82.     lli ans = 0;
  83.    
  84.     // cout<<top.size()<<" "<<bot.size()<<" "<<two.size()<<"\n";
  85.    
  86.     int ts = top.size() , bs = bot.size() , ws = two.size();
  87.    
  88.     if ( (top.size() == 1) && (bot.size()+two.size() == 0) )
  89.     {
  90.         int t = *top.begin();
  91.         for (int i=1 ; i<=n ; i++)
  92.         {
  93.             ans += check( i , t );
  94.         }
  95.     }
  96.     else if ( (bot.size() == 1) && (top.size()+two.size() == 0) )
  97.     {
  98.         int t = *bot.begin();
  99.         for (int i=1 ; i<=n ; i++)
  100.         {
  101.             ans += check( i , t );
  102.         }
  103.     }
  104.     else if ( ts==1 && bs==1 && ws==0 )
  105.     {
  106.         int t = *top.begin();
  107.         int b = *bot.begin();
  108.         ans += check( t , b );
  109.     }
  110.     else if ( ts==1 && bs==0 && ws==1 )
  111.     {
  112.         int t = *top.begin();
  113.         int w1 = *two.begin();
  114.         int w2 = w1 + 1;
  115.        
  116.         ans += check( t , w1 );
  117.         ans += check( t , w2 );
  118.     }
  119.     else if ( ts==0 && bs==1 && ws==1 )
  120.     {
  121.         int b = *bot.begin();
  122.         int w1 = *two.begin();
  123.         int w2 = w1 + 1;
  124.        
  125.         ans += check( b , w1 );
  126.         ans += check( b , w2 );
  127.     }
  128.     else if ( ts==0 && bs==0 && ws==2 )
  129.     {
  130.         int w1 = *two.begin();
  131.         int w2 = w1 + 1;
  132.         int w3 = *(++two.begin());
  133.         int w4 = w3 + 1;
  134.        
  135.         ans += check( w1 , w3 );
  136.         ans += check( w1 , w4 );
  137.         ans += check( w2 , w3 );
  138.         ans += check( w2 , w4 );
  139.     }
  140.     else if ( ts==0 && bs==0 && ws==1 )
  141.     {
  142.         int w1 = *two.begin();
  143.         int w2 = w1 + 1;
  144.        
  145.         for (int i=1 ; i<=n ; i++)
  146.             ans += check( i , w1 );
  147.        
  148.         for (int i=1 ; i<=n ; i++)
  149.             ans += check( i , w2 );
  150.        
  151.         ans -= check(w1 , w2);
  152.     }
  153.    
  154.     cout<<ans<<"\n";
  155.    
  156.     return 0;
  157. }
RAW Paste Data