Submission #198302

#	Time	Username	Problem	Language	Result	Execution time	Memory
198302		MiricaMatei	Santa Claus (RMI19_santa)	C++14	0 / 100	293 ms	10616 KiB

santa

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;

struct Cadou {
  int p, val, pt;

  bool operator <(const Cadou& other) const {
    if (val == other.val)
      return p < other.p;
    return val < other.val;
  }
}cd[MAXN], cp[MAXN];

int x[MAXN], h[MAXN], v[MAXN];

void solve() {
  int n, cad = 0, cop = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &x[i]);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &h[i]);
  int lst = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
    if (!h[i])
      cd[++cad] = {x[i], v[i], 0}, lst = i;
  }
  sort(cd + 1, cd + cad + 1);
  multiset<int>s;
  int j = 1, l1 = 1;
  for (int i = 1; i <= n && j <= cad; ++i) {
    if (h[i] == 1) {
      s.insert(v[i]);
      cp[++cop] = {x[i], v[i], 0};
    }
    while (j <= cad && !s.empty() && (*s.begin()) <= cd[j].val) {
      j++;
      s.erase(s.begin());
    }
    l1 = i;
  }
  if (j <= cad) {
    for (int i = 1; i <= n; ++i)
      printf("-1 ");
    printf("\n");
    return ;
  }
  lst = max(l1, lst);
  sort(cp + 1, cp + cop + 1);
  set<int>pq;
  int i1 = 1;
  j = 1;
  multiset<pair<int, int> >s1;
  while (j <= cad) {
    while (i1 <= cop && cp[i1].val <= cd[j].val) {
      pq.insert(cp[i1].p);
      i1++;
    }
    set<int>::iterator it = pq.lower_bound(cd[j].p);
    if (it == pq.end())
      it--;
    cd[j].pt = (*it);
    if (cd[j].pt < cd[j].p)
      s1.insert({cd[j].pt, cd[j].val});
    pq.erase(it);
    j++;
  }
  for (int i = 1; i < lst; ++i)
    printf("-1 ");
  if (lst <= n) {
    if (s1.empty()) {
      printf("%d ", x[lst]);
    } else {
      printf("%d ", 2 * x[lst] - (*s1.begin()).first);
    }
  }
  for (int i = lst + 1; i <= n; ++i) {
    if (h[i] == 1) {
      if (!s1.empty()) {
        pair<int, int>aux = *s1.begin();
        if (aux.second >= v[i])
          s1.erase(s1.begin());
      }
    }
    if (s1.empty()) {
      printf("%d ", x[i]);
    } else {
      printf("%d ", 2 * x[i] - (*s1.begin()).first);
    }
  }
  printf("\n");
}

int main() {

  int t;
  scanf("%d", &t);
  while (t--)
    solve();

  return 0;
}

Compilation message (stderr)

santa.cpp: In function 'void solve()':
santa.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
santa.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x[i]);
     ~~~~~^~~~~~~~~~~~~
santa.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &h[i]);
     ~~~~~^~~~~~~~~~~~~
santa.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &v[i]);
     ~~~~~^~~~~~~~~~~~~
santa.cpp: In function 'int main()':
santa.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 100