Submission #226787

#	Time	Username	Problem	Language	Result	Execution time	Memory
226787		quocnguyen1012	Zoltan (COCI16_zoltan)	C++14	140 / 140	156 ms	10188 KiB

zoltan

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, mod = 1e9 + 7, base = 31;

ii bit[2][maxn];
int N, a[maxn];
vector<int> val;
int f[2][maxn];
int cnt[2][maxn];

void upd(int id, int i, int v, int way)
{
  for(; i <= (int)val.size(); i += i & -i){
    if(bit[id][i].fi < v){
      bit[id][i] = mp(v, way);
    }
    else if(bit[id][i].fi == v){
      bit[id][i].se += way;
      bit[id][i].se %= mod;
    }
  }
}

ii query(int id, int i)
{
  ii ans = mp(0, 1);
  for(; i; i -= i & -i){
    if(ans.fi == bit[id][i].fi){
      ans.se += bit[id][i].se;
      ans.se %= mod;
    }
    else if(ans.fi < bit[id][i].fi){
      ans = bit[id][i];
    }
  }
  return ans;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  ii res = mp(0, 0);
  cin >> N;
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
    val.eb(a[i]);
  }
  sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
  for(int i = 1; i <= N; ++i){
    a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
  }
  for(int i = N; i >= 1; --i){
    auto ret = query(0, a[i] - 1);
    int ways = ret.se;
    if(f[0][a[i]] < ret.fi + 1){
      f[0][a[i]] = ret.fi + 1;
      cnt[0][a[i]] = ret.se;
      upd(0, a[i], f[0][a[i]], cnt[0][a[i]]);
    }
    else if(f[0][a[i]] == ret.fi + 1){
      cnt[0][a[i]] += ret.se;
      cnt[0][a[i]] %= mod;
      upd(0, a[i], f[0][a[i]], ret.se);
    }
    ret = query(1, val.size() - a[i]);
    ways = 1ll * ways * ret.se % mod;
    if(f[1][a[i]] < ret.fi + 1){
      f[1][a[i]] = ret.fi + 1;
      cnt[1][a[i]] = ret.se;
      upd(1, val.size() - a[i] + 1, f[1][a[i]], cnt[1][a[i]]);
    }
    else if(f[1][a[i]] == ret.fi + 1){
      cnt[1][a[i]] += ret.se;
      cnt[1][a[i]] %= mod;
      upd(1, val.size() - a[i] + 1, f[1][a[i]], ret.se);
    }
    if(f[0][a[i]] + f[1][a[i]] - 1 > res.fi){
      res.fi = f[0][a[i]] + f[1][a[i]] - 1;
      res.se = ways;
    }
    else if(f[0][a[i]] + f[1][a[i]] - 1 == res.fi){
      res.se += ways;
      res.se %= mod;
    }
  }
  for(int i = res.fi + 1; i <= N; ++i){
    res.se = 2ll * res.se % mod;
  }
  cout << res.fi << ' ' << res.se;
}

• Subtask 1: 140 / 140