Submission #645859

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
645859	2022-09-28T07:57:01 Z	Alex_tz307	Santa Claus (RMI19_santa)	C++17	100 / 100	246 ms	13592 KB

santa

#include <bits/stdc++.h>

using namespace std;

struct node {
  int sum, minSum;
};

struct ST {
  int n;
  vector<node> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void update(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      t[x].sum += v;
      t[x].minSum += v;
      return;
    }

    int mid = (lx + rx) / 2;

    if (pos <= mid) {
      update(x * 2, lx, mid, pos, v);
    } else {
      update(x * 2 + 1, mid + 1, rx, pos, v);
    }

    t[x].sum = t[x * 2].sum + t[x * 2 + 1].sum;
    t[x].minSum = min(t[x * 2].minSum, t[x * 2].sum + t[x * 2 + 1].minSum);
  }

  void update(int pos, int v) {
    update(1, 1, n, pos, v);
  }

  int minPref() {
    return t[1].minSum;
  }
};

void testCase() {
  int n;
  cin >> n;

  vector<int> x(n + 1), h(n+ 1), v(n + 1);

  for (int i = 1; i <= n; ++i) {
    cin >> x[i];
  }

  for (int i = 1; i <= n; ++i) {
    cin >> h[i];
  }

  for (int i = 1; i <= n; ++i) {
    cin >> v[i];
    v[i] += 1;
  }

  vector<int> elf(n + 1);
  multiset<int> presents;
  for (int i = 1; i <= n; ++i) {
    if (h[i] == 0) {
      presents.emplace(v[i]);
    } else {
      auto it = presents.lower_bound(v[i]);
      if (it != presents.end()) {
        elf[i] = *it;
        presents.erase(it);
      }
    }
  }

  int last = 0;
  for (int i = 1; i <= n; ++i) {
    if (h[i] == 0) {
      last = i;
    }
  }

  ST t(n + 1);

  int r;
  for (r = 1; r <= n; ++r) {
    if (h[r] == 0) {
      t.update(v[r], -1);
    } else {
      t.update(v[r], 1);
    }
    if (r >= last && t.minPref() >= 0) {
      break;
    }
  }

  vector<int> sol(n + 1, -1);

  int l = 1;
  while (r <= n) {
    while (l < r) {
      if (h[l] == 1) {
        t.update(v[l], -1);
        if (elf[l]) {
          t.update(elf[l], 1);
        }
        if (t.minPref() < 0) {
          t.update(v[l], 1);
          if (elf[l]) {
            t.update(elf[l], -1);
          }
          break;
        }
      }
      l += 1;
    }

    sol[r] = 2 * x[r] - x[l];

    if (r + 1 <= n) {
      t.update(v[r + 1], 1);
    }

    r += 1;
  }

  for (int i = 1; i <= n; ++i) {
    cout << sol[i] << ' ';
  }
  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	5 ms	468 KB	Output is correct
4	Correct	14 ms	852 KB	Output is correct
5	Correct	27 ms	1556 KB	Output is correct
6	Correct	47 ms	2564 KB	Output is correct
7	Correct	86 ms	4660 KB	Output is correct
8	Correct	126 ms	7116 KB	Output is correct
9	Correct	168 ms	10168 KB	Output is correct
10	Correct	246 ms	13592 KB	Output is correct