oj.uz

Submission #226787

# Submission time Handle Problem Language Result Execution time Memory
226787 2020-04-25T10:33:19 Z quocnguyen1012 Zoltan (COCI16_zoltan) C++14
140 / 140
 156 ms 10188 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 79 ms 7920 KB Output is correct
12 Correct 70 ms 6892 KB Output is correct
13 Correct 65 ms 6532 KB Output is correct
14 Correct 106 ms 7280 KB Output is correct
15 Correct 124 ms 8816 KB Output is correct
16 Correct 156 ms 10188 KB Output is correct
17 Correct 105 ms 8556 KB Output is correct
18 Correct 107 ms 8560 KB Output is correct
19 Correct 105 ms 8560 KB Output is correct
20 Correct 104 ms 8608 KB Output is correct