Submission #1182722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182722		zNatsumi	Zoltan (COCI16_zoltan)	C++20	140 / 140	80 ms	5052 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int n, a[N];
vector<int> rrh;

void add(int &x, int y){
  x += y;
  if(x >= mod) x -= mod;
  if(x < 0) x += mod;
}

namespace bit1{
  ii bit[N];

  void update(int i, int x, int c){
    for(; i <= n; i += i & -i){
      if(x == bit[i].first) add(bit[i].second, c);
      else if(x > bit[i].first) bit[i] = {x, c};
    }
  }
  ii get(int i){
    ii res = {0, 0};
    for(; i > 0; i -= i & -i){
      if(bit[i].first > res.first) res = bit[i];
      else if(bit[i].first == res.first) add(res.second, bit[i].second);
    }
    return res;
  }
}

namespace bit2{
  ii bit[N];

  void update(int i, int x, int c){
    for(; i > 0; i -= i & -i){
      if(x == bit[i].first) add(bit[i].second, c);
      else if(x > bit[i].first) bit[i] = {x, c};
    }
  }
  ii get(int i){
    ii res = {0, 0};
    for(; i <= n; i += i & -i){
      if(bit[i].first > res.first) res = bit[i];
      else if(bit[i].first == res.first) add(res.second, bit[i].second);
    }
    return res;
  }
}


int pow(int x, int y){
  int res = 1LL;
  while(y){
    if(y & 1) res = 1LL * res * x % mod;
    x = 1LL * x * x % mod;
    y >>= 1;
  }
  return res;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];

  for(int i = 1; i <= n; i++) rrh.push_back(a[i]);
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());
  for(int i = 1; i <= n; i++) a[i] = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1;

  int MX = 0, cnt = 0;
  for(int i = n; i >= 1; i--){
    auto x = max(bit1::get(a[i] - 1), make_pair(0, 1));
    auto y = max(bit2::get(a[i] + 1), make_pair(0, 1));

    bit1::update(a[i], x.first + 1, x.second);
    bit2::update(a[i], y.first + 1, y.second);

    if(x.first + y.first + 1 > MX){
      MX = x.first + y.first + 1;
      cnt = 1LL * x.second * y.second % mod;
    }
    else if(x.first + y.first + 1 == MX){
      cnt = (cnt + 1LL * x.second * y.second % mod)%mod;
    }
  }
  cout << MX << " " << 1LL * cnt * pow(2, n - MX) % mod << "\n";
}

• Subtask 1: 140 / 140