Submission #833307

#	Time	Username	Problem	Language	Result	Execution time	Memory
833307		vjudge1	Exam (eJOI20_exam)	C++17	0 / 100	1079 ms	36992 KiB

exam

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// using ld = long double;
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...)
#endif

template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B> &p);
template<class T> ostream& operator<<(ostream& os, const vector<T> &v);
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N> &v);

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
  return os << '(' << p.first << ',' << p.second << ')';
}
 
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
  os << '{'; bool fs = 1;
  for(auto &i : v) { if(!fs) os << ','; os << i; fs = 0; }
  return os << '}';
}

template<class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N> &v) {
  os << '{'; bool fs = 1;
  for(auto &i : v) { if(!fs) os << ','; os << i; fs = 0; }
  return os << '}';
}

template<class T>
struct SparseTable {
  int sz;
  vector<vector<T>> st;

  void init(vector<T> &a) {
    sz = a.size();
    int lg = __lg(sz);
    st.resize(lg+1);

    st[0].resize(sz);
    for(int i = 0; i < sz; i++) {
      st[0][i] = a[i];
    }

    for(int i = 1; i <= lg; i++) {
      st[i].resize(sz - (1<<(i-1)));
      for(int j = 0; j + (1<<i) - 1 < sz; j++) {
        st[i][j] = max(st[i-1][j], st[i-1][j + (1<<(i-1))]);
      }
    }
  }

  T query(int l, int r) {
    int lg = __lg(r-l+1);
    return max(st[lg][l], st[lg][r-(1<<lg)+1]);
  }
};


void init() {
}
 
void solve(int tt = 0) {
  int n; cin >> n;
  vector<ll> h(n), t(n);
  for(ll &i : h) cin >> i;
  for(ll &i : t) cin >> i;

  // build cartesian tree
  vector<pair<ll, int>> h2(n);
  for(int i = 0; i < n; i++)
    h2[i] = {h[i], i};
  SparseTable<pair<ll, int>> st;
  st.init(h2);

  int nn = 0;
  vector<int> dp(n);
  vector<int> lb(n), rb(n);
  const auto dnc = [&](const auto &dnc, int l, int r) -> pair<int, int> {
    if(l > r) return {-1, -1};
    int idx = nn++;
    lb[idx] = l, rb[idx] = r;
    auto [mx, mxid] = st.query(l, r);
    auto [mxl, lc] = dnc(dnc, l, mxid-1);
    auto [mxr, rc] = dnc(dnc, mxid+1, r);
    debug(cerr << "l = " << l << ' ' << "r = " << r << " mxid = " << mxid << '\n');
    debug(cerr << " lc = " << lc << " rc = " << rc << '\n');

    int cntnw = (mx == t[mxid]);
    int cntl = 0, cntr = 0;
    if(lc != -1) {
      for(int i = l; i < mxid; i++) {
        debug(cerr << ' ' << h[i]);
        if(t[i] == mx) cntl++;
      }
      debug(cerr << '\n');
    }
    if(rc != -1) {
      for(int i = mxid+1; i <= r; i++) {
        debug(cerr << ' ' << h[i]);
        if(t[i] == mx) cntr++;
      }
      debug(cerr << '\n');
    }
    dp[idx] = cntnw + max(cntl, (lc == -1 ? 0 : dp[lc])) + max(cntr, (rc == 0 ? -1 : dp[rc]));
    debug(cerr << " cntnw = " << cntnw << " cntl = " << cntl << " cntr = " << cntr << '\n');
    debug(cerr << " dp[lc] = " << (lc == -1 ? 0 : dp[lc]) << " dp[rc] = " << (rc == -1 ? 0 : dp[rc]) << '\n');
    debug(cerr << " ans = " << dp[idx] << '\n');
    return {mxid, idx};
  };
  dnc(dnc, 0, n-1);
  cout << dp[0] << '\n';
}

void reset() {
}
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; // cin >> t;
  init();
  for(int i = 1; i <= t; i++) solve(i), reset();
  return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22