Submission #833434

#	Time	Username	Problem	Language	Result	Execution time	Memory
833434		vjudge1	Exam (eJOI20_exam)	C++17	12 / 100	16 ms	1492 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<int> h(n), t(n);
  for(int &i : h) cin >> i;
  for(int &i : t) cin >> i;

  int x = t[0];
  const auto cmp = [&](int i) { return x == i; };
  vector<int> idx;
  for(auto it = h.begin(); (it = find_if(it, h.end(), cmp)) != h.end(); it++) {
    idx.push_back((int)(it - h.begin()));
  }
  debug(cerr << idx << '\n');
  const auto fill = [&](const auto &fill, int i) -> void{
    if(i > 0 && h[i-1] < x) h[i-1] = x, fill(fill, i-1);
    if(i < n-1 && h[i+1] < x) h[i+1] = x, fill(fill, i+1);
  };
  for(int i : idx) fill(fill, i);
  int ans = 0;
  for(int i = 0; i < n; i++)
    ans += h[i] == t[i];
  cout << ans << '\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: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22