제출 #1286323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286323		LIA	Zoltan (COCI16_zoltan)	C++17	14 / 140	327 ms	37500 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define loop(i, s, e) for (ll i = s; i < e; ++i)
#define pll pair<ll, ll>
const ll inf = 1e9 + 7;
struct Seg {
  ll sz = 1;
  vector<pll> seg;
  Seg(ll n) {
    for (; sz < n; sz *= 2)
      ;
    seg.resize(sz * 2, {0, 0});
  }
  static inline pll mg(pll a, pll b) {
    if (a.first > b.first)
      return a;
    if (b.first > a.first)
      return b;
    if (a.first == 0)
      return {0, 0};
    return {a.first, (a.second + b.second) % inf};
  }
  void update(ll p, ll v, ll w) {
    p += sz;
    if (seg[p].first < v)
      seg[p] = {v, w % inf};
    else if (seg[p].first == v)
      seg[p].second = (seg[p].second + w) % inf;
    for (p /= 2; p > 0; p /= 2)
      seg[p] = mg(seg[p * 2], seg[p * 2 + 1]);
  }
  pll query(ll l, ll r) {
    if (r < l)
      return {0, 0};
    l += sz, r += sz;
    pll L = {0, 0}, R = {0, 0};
    while (l <= r) {
      if (l & 1)
        L = mg(L, seg[l++]);
      if (!(r & 1))
        R = mg(seg[r--], R);
      l /= 2, r /= 2;
    }
    return mg(L, R);
  }
};

ll fp(ll a, ll e) {
  ll r = 1 % inf;
  while (e) {
    if (e & 1)
      r = (r * a) % inf;
    a = (a * a) % inf;
    e >>= 1;
  }
  return r;
}

int main() {
  ll n;
  cin >> n;
  vll arr(n), vals;
  vector<pll> dp(n);
  ll mx = 0, ways = 0;

  loop(i, 0, n) {
    cin >> arr[i];
    vals.push_back(arr[i]);
  }

  vll comp = vals;
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  ll K = comp.size();
  auto id = [&](ll x) { return (lower_bound(comp.begin(), comp.end(), x) - comp.begin()); };

  vector<vector<ll>> pos(K);
  loop(i, 0, n) pos[id(arr[i])].push_back(i);

  vector<pll> L(n), Rv(n);

  {
    Seg seg(K + 5);
    loop(v, 0, K) {
      vector<pair<ll, pll>> upd;
      for (ll i : pos[v]) {
        pll q = seg.query(0, v - 1);
        if (q.first == 0)
          q.second = 1;
        L[i] = {q.first + 1, q.second % inf};
        upd.push_back({v, L[i]});
      }
      for (auto& t : upd)
        seg.update(t.first, t.second.first, t.second.second);
    }
  }

  {
    Seg seg(K + 5);
    for (ll v = K - 1; v >= 0; --v) {
      vector<pair<ll, pll>> upd;
      for (ll i = pos[v].size() - 1; i >= 0; --i) {
        ll idx = pos[v][i];
        pll q = seg.query(v + 1, K - 1);
        if (q.first == 0)
          q.second = 1;
        Rv[idx] = {q.first + 1, q.second % inf};
        upd.push_back({v, Rv[idx]});
      }
      for (auto& t : upd)
        seg.update(t.first, t.second.first, t.second.second);
    }
  }

  ll R = 0;
  loop(i, 0, n) R = max(R, L[i].first + Rv[i].first - 1);

  unordered_map<ll, pll> bestAt;
  loop(i, 0, n) {
    if (L[i].first + Rv[i].first - 1 == R) {
      ll key = id(arr[i]);
      pll cur = bestAt[key];
      pll add = {L[i].first + Rv[i].first - 1, (L[i].second * Rv[i].second) % inf};
      if (cur.first < add.first)
        bestAt[key] = add;
      else if (cur.first == add.first)
        bestAt[key] = {cur.first, (cur.second + add.second) % inf};
    }
  }

  ll sumWays = 0;
  for (auto& kv : bestAt)
    sumWays = (sumWays + kv.second.second) % inf;
  ll freeCnt = n - R;
  ll mult = fp(2, freeCnt);
  ll ansWays = (sumWays * mult) % inf;

  cout << R << " " << ansWays << "\n";
  return 0;
}

• Subtask 1: 14 / 140