Submission #331924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
331924	2020-11-30T18:12:39 Z	AlexPop28	Santa Claus (RMI19_santa)	C++11	100 / 100	320 ms	10600 KB

santa

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

struct SegmTree {
  int n;
  vector<int> t, lazy;
  SegmTree(int n_) : n(n_) {
    int sz = 1;
    while (sz < 2 * n) sz *= 2;
    t.resize(sz);
    lazy.resize(sz);
  }

  void Push(int node) {
    for (int son : {2 * node + 1, 2 * node + 2}) {
      t[son] += lazy[node];
      lazy[son] += lazy[node];
    }
    lazy[node] = 0;
  }

  void Pull(int node) {
    t[node] = min(t[2 * node + 1], t[2 * node + 2]);
  }

  void Add(int node, int left, int right, int x, int y, int val) {
    if (y < left || right < x) return;
    if (x <= left && right <= y) {
      t[node] += val;
      lazy[node] += val;
      return;
    }
    Push(node);
    int mid = (left + right) / 2;
    Add(2 * node + 1, left, mid, x, y, val);
    Add(2 * node + 2, mid + 1, right, x, y, val);
    Pull(node);
  }

  void AddSuff(int l, int val) {
    Add(0, 0, n - 1, l, n - 1, val);
  }

  int GetMin() {
    return t[0];
  }
};

void SolveTest() {
  int n; cin >> n;
  vector<int> x(n), h(n), v(n);
  for (int &a : x) cin >> a;
  for (int &a : h) cin >> a;
  for (int &a : v) cin >> a;

  auto all = v;
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());

  for (int &a : v) a = lower_bound(all.begin(), all.end(), a) - all.begin();

  SegmTree st(all.size());

  int last_elf = n - 1;
  while (last_elf >= 0 && h[last_elf]) --last_elf;

  if (last_elf < 0) {
    for (int i = 0; i < n; ++i) {
      cout << 2 * x[i] << ' ';
    }
    cout << '\n';
    return;
  }

  auto Push = [&](int pos) {
    if (h[pos]) st.AddSuff(v[pos], +1);
    else st.AddSuff(v[pos], -1);
  };

  vector<int> ans(n, -1);
  int right = 0;
  while (right <= last_elf) Push(right++);

  map<int, int> elves;
  for (int left = 0; left < n; ++left) {
    if (left == right) Push(right++);
    while (right < n && st.GetMin() < 0) Push(right++);

    if (st.GetMin() >= 0) ans[right - 1] = left; // we have a valid bracket sequence

    if (!h[left]) {
      elves[v[left]] += 1;
    } else {
      auto it = elves.lower_bound(v[left]);
      if (it != elves.end()) {
        st.AddSuff(it->first, +1);
      }
      if (--it->second == 0) elves.erase(it);
      st.AddSuff(v[left], -1);
    }
  }

  for (int i = 1; i < n; ++i) {
    ans[i] = max(ans[i], ans[i - 1]);
  }

  for (int i = 0; i < n; ++i) {
    if (ans[i] == -1) cout << "-1 ";
    else cout << 2 * x[i] - x[ans[i]] << ' ';
  }
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t; cin >> t;
  while (t--) {
    SolveTest();
  }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	7 ms	640 KB	Output is correct
4	Correct	16 ms	1024 KB	Output is correct
5	Correct	37 ms	1516 KB	Output is correct
6	Correct	63 ms	2284 KB	Output is correct
7	Correct	115 ms	4332 KB	Output is correct
8	Correct	181 ms	6252 KB	Output is correct
9	Correct	228 ms	6996 KB	Output is correct
10	Correct	320 ms	10600 KB	Output is correct