oj.uz

Submission #636936

# Submission time Handle Problem Language Result Execution time Memory
636936 2022-08-30T15:02:33 Z rockoana medians (balkan11_medians) C++17
75 / 100
 300 ms 16736 KB 
/*
                    __
                   /\ \
 _ __   ___     ___\ \ \/'\     ___      __      ___     ___      __
/\`'__\/ __`\  /'___\ \ , <    / __`\  /'__`\  /' _ `\ /' _ `\  /'__`\
\ \ \//\ \L\ \/\ \__/\ \ \\`\ /\ \L\ \/\ \L\.\_/\ \/\ \/\ \/\ \/\ \L\.\_
 \ \_\\ \____/\ \____\\ \_\ \_\ \____/\ \__/.\_\ \_\ \_\ \_\ \_\ \__/.\_\
  \/_/ \/___/  \/____/ \/_/\/_/\/___/  \/__/\/_/\/_/\/_/\/_/\/_/\/__/\/_/


*/

#ifndef __AHA__HEADER
#define __AHA__HEADER

#include <bits/stdc++.h>
using namespace std;
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define ft first
#define sd second
#define sz(x) (i6) x.size()
#define psb(x) push_back(x)
#define ppb() pop_back()
#define bg(x) x.begin()
#define ed(x) x.end()
#define col(x) x.begin(), x.end()
#define srt(x) sort(x.begin(), x.end())

#define pq priority_queue
#define fn function
#ifdef LOCAL
#define git stauDBG_MACRO_NO_WARNING
#include <dbg.h>
#else
#define dbg(...)
#endif
#define endl '\n'

template <typename T>
using vec = vector<T>;
template <typename T>
using deq = deque<T>;
template <typename K, typename V>
using hmap = unordered_map<K, V>;

using str = string;
using vb = vec<bool>;

using byte = int8_t;
using i3 = int32_t;
using i6 = int64_t;
using i64 = int64_t;
using u3 = uint32_t;
using u6 = uint64_t;

using d6 = long double;

using p3 = pair<i3, i3>;
using vi3 = vec<i3>;
using vp3 = vec<p3>;

using p6 = pair<i6, i6>;
using vi6 = vec<i6>;
using vd6 = vec<d6>;
using vp6 = vec<p6>;
using vv = vec<vi6>;

using dp6 = deq<p6>;
using di6 = deq<i6>;

using mi6 = map<i6, i6>;
using mp6 = map<p6, i6>;
using si6 = set<i6>;
using hi6 = hmap<i6, i6>;

using bs = bitset<64>;

using graph = vv;
using matrix = vv;

const d6 EPS = 1 / 1000000.0;
const i6 ZERO = 0;
const i6 _0 = ZERO;
const i6 ONE = 1;
const i6 _1 = ONE;
const i6 INF = INT64_MAX / 4;
const i6 NINF = -INF;

namespace std {
template <typename T1, typename T2>
struct hash<pair<T1, T2>> {
  std::size_t operator()(const pair<T1, T2>& pair) const noexcept {
    return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
  }
};
}  // namespace std

template <typename T1, typename T2>
istream& operator>>(istream& stream, pair<T1, T2>& p) {
  stream >> p.ft;
  stream >> p.sd;
  return stream;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
  return stream << p.ft << " " << p.sd;
}

template <typename T>
istream& operator>>(istream& stream, vec<T>& v) {
  if (v.empty()) {
    u6 len;
    stream >> len;
    v.assign(len, T());
  }
  for (auto i = 0; i < sz(v); i++) {
    stream >> v[i];
  }
  return stream;
}

template <typename T>
ostream& operator<<(ostream& stream, const vec<T>& v) {
  if (!v.empty()) {
    stream << v[0];
  }
  for (auto i = 1; i < sz(v); i++) {
    stream << " " << v[i];
  }
  return stream;
}

template <typename T>
istream& operator>>(istream& stream, deq<T>& v) {
  if (v.empty()) {
    u6 len;
    stream >> len;
    v.assign(len, T());
  }
  for (auto i = 0; i < sz(v); i++) {
    stream >> v[i];
  }
  return stream;
}

template <typename T>
ostream& operator<<(ostream& stream, const deq<T>& v) {
  if (!v.empty()) {
    stream << v[0];
  }
  for (auto i = 1; i < sz(v); i++) {
    stream << " " << v[i];
  }
  return stream;
}
#endif

inline u6 nexp2(i6 n) {
  u6 res = 1;
  while ((i6)res < n) {
    res = res * 2;
  }
  return res;
}

class segtree {
 private:
  fn<i6(i6, i6)> f;
  i6 def_val;
  u6 offset;
  vi6 data;

 public:
  segtree(u6 n, fn<i6(i6, i6)> fun, i6 def_value)
      : f(fun), def_val(def_value), offset(nexp2(n + 1)) {
    data.assign(offset * 2, def_val);
  }

  inline void set(u6 i, i6 x) {
    auto crt = i + offset;
    data[crt] = x;
    crt /= 2;
    while (crt > 0) {
      data[crt] = f(data[2 * crt], data[2 * crt + 1]);
      crt = crt / 2;
    }
  }

  i6 rmq(u6 left, u6 right) {
    left += offset;
    right += offset + 1;

    i6 res_l = def_val;
    i6 res_r = def_val;

    while (left < right) {
      if (left % 2 == 1) {
        res_l = f(res_l, data[left++]);
      }

      if (right % 2 == 1) {
        res_r = f(data[--right], res_r);
      }
      left /= 2;
      right /= 2;
    }
    return f(res_l, res_r);
  }

  // if you want to reuse an existing seg tree
  void reset(u6 n) {
    offset = nexp2(n + 1);
    data.assign(offset * 2, def_val);
  }

  // if you want to do multiple sets followed by one update
  void update() {
    for (i6 i = offset - 1; i > 0; i--) {
      data[i] = f(data[2 * i], data[2 * i + 1]);
    }
  }

  inline void put(u6 i, i6 x) {
    auto crt = i + offset;
    data[crt] = x;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // #ifdef LOCAL
  // ifstream cin{"medians.in"};
  // ofstream cout{"medians.out"};
  // #endif

  i64 n;
  cin >> n;

  vi6 b(n + 1);
  for (i64 i = 1; i <= n; i++) {
    cin >> b[i];
  }

  si6 left;
  for (i64 i = 1; i < 2 * n; i++) {
    left.insert(i);
  }

  vi6 a(2 * n);
  segtree s(
      2 * n, [](i64 x, i64 y) { return x + y; }, 0);

  a[1] = b[1];
  left.erase(a[1]);
  s.set(a[1], 1);
  i64 last = 2;
  for (i64 i = 2; i <= n && !left.empty() && last < 2 * n; i++) {
    if (left.find(b[i]) != left.end()) {
      s.set(b[i], 1);
      a[last] = b[i];
      last++;
      left.erase(b[i]);
    }

    i64 sl = s.rmq(1, b[i]) - 1;
    i64 sr = s.rmq(b[i], 2 * n - 1) - 1;
    if (sl > sr) {
      while (sl > sr && last < 2 * n) {
        auto it = (--left.end());
        s.put(*it, 1);
        a[last] = *it;
        last++;
        left.erase(it);
        sr++;
      }
      s.update();
    } else if (sr > sl) {
      while (sr > sl && last < 2 * n) {
        auto it = left.begin();
        s.put(*it, 1);
        a[last] = *it;
        last++;
        left.erase(it);
        sl++;
      }
      s.update();
    }

    if (sr == sl && sr + sl + 1 != 2 * i - 1) {
      i64 crt = 0;
      while (sr + sl + 1 != 2 * i - 1) {
        auto it = left.begin();
        if (crt % 2) {
          it = (--left.end());
          sr++;
        } else {
          sl++;
        }
        s.put(*it, 1);
        a[last] = *it;
        last++;
        left.erase(it);
        crt++;
      }
      s.update();
    }
  }

  for (i64 i = 1; i < 2 * n; i++) {
    cout << a[i];
    if (i + 1 != 2 * n) {
      cout << " ";
    }
  }

  return 0;
}

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 7 ms 436 KB Output is correct

Subtask #2
10.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 628 KB Output is correct
2 Correct 92 ms 936 KB Output is correct
3 Execution timed out 381 ms 1548 KB Time limit exceeded
4 Execution timed out 1093 ms 2752 KB Time limit exceeded
5 Execution timed out 1092 ms 5252 KB Time limit exceeded
6 Execution timed out 1088 ms 10208 KB Time limit exceeded
7 Execution timed out 1080 ms 16736 KB Time limit exceeded