oj.uz

Submission #864474

# Submission time Handle Problem Language Result Execution time Memory
864474 2023-10-23T04:00:29 Z NeroZein Zoltan (COCI16_zoltan) C++17
140 / 140
 278 ms 18364 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;
const int md = (int) 1e9 + 7; 

int a[N], p2[N]; 
pair<int, int> seg[N * 2];
pair<int, int> lis[N], lds[N]; 

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

int mul(int x, int y) {
  return (int) ((long long) x * y % md); 
}

pair<int, int> comb(pair<int,int> x, pair<int,int> y) {
  if (x.first == y.first) {
    return {x.first, (x.second + y.second) % md};
  }
  return max(x, y); 
}

void upd(int nd, int l, int r, int p, pair<int, int> v) {
  if (l == r) {
    seg[nd] = v; 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = comb(seg[nd + 1], seg[rs]); 
}

pair<int, int> qry(int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e); 
    } else {
      return comb(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  p2[0] = 1;
  for (int i = 1; i < N; ++i) {
    p2[i] = mul(p2[i - 1], 2); 
  }
  int n;
  cin >> n;
  map<int, int> mp; 
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    mp[a[i]];
  }
  int cnt = 0;
  for (auto& it : mp) {
    it.second = cnt++; 
  }
  for (int i = 0; i < n; ++i) {
    a[i] = mp[a[i]]; 
  }
  vector<int> id(n);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] > a[j]; 
  });
  upd(0, 0, n, n, {0, 1}); 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lis[ind] = qry(0, 0, n, ind, n);
    lis[ind].first++; 
    upd(0, 0, n, ind, lis[ind]); 
  }
  for (int i = 0; i < N * 2; ++i) {
    seg[i] = {0, 0}; 
  }
  sort(id.begin(), id.end(), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j]; 
  });
  int mx = 1; 
  upd(0, 0, n, n, {0, 1}); 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lds[ind] = qry(0, 0, n, ind, n);
    lds[ind].first++;
    upd(0, 0, n, ind, lds[ind]); 
    mx = max(mx, lis[ind].first + lds[ind].first - 1); 
  }
  cnt = 0; 
  for (int i = 0; i < n; ++i) {
    if (lis[i].first + lds[i].first == mx + 1) {
      add(cnt, mul(p2[n - mx], mul(lds[i].second, lis[i].second)));
    }
  }
  cout << mx << ' ' << cnt << '\n'; 
  return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 3 ms 7332 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct
8 Correct 3 ms 7260 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 165 ms 15700 KB Output is correct
12 Correct 134 ms 14448 KB Output is correct
13 Correct 133 ms 13936 KB Output is correct
14 Correct 189 ms 14420 KB Output is correct
15 Correct 226 ms 16464 KB Output is correct
16 Correct 278 ms 18364 KB Output is correct
17 Correct 173 ms 16724 KB Output is correct
18 Correct 172 ms 16872 KB Output is correct
19 Correct 185 ms 16984 KB Output is correct
20 Correct 174 ms 16708 KB Output is correct