oj.uz

Submission #833434

# Submission time Handle Problem Language Result Execution time Memory
833434 2023-08-22T05:35:20 Z vjudge1 Exam (eJOI20_exam) C++17
12 / 100
 16 ms 1492 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 13 ms 980 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 15 ms 1236 KB Output is correct
6 Correct 8 ms 1492 KB Output is correct
7 Correct 9 ms 1108 KB Output is correct
8 Correct 16 ms 1120 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -