Submission #636980

#	Time	Username	Problem	Language	Result	Execution time	Memory
636980		abeker	Measures (CEOI22_measures)	C++17	100 / 100	276 ms	23320 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int MAXN = 4e5 + 5;
const ll INF = 1e15;

struct Node {
  ll mini, maks, diff, lazy;
  Node(ll mini, ll maks, ll diff, ll lazy) : 
    mini(mini), maks(maks), diff(diff), lazy(lazy) {}
  Node() : mini(INF), maks(-INF), diff(-INF), lazy(0) {}
};

class Tournament {
  int offset;
  vector <Node> tour;
public:
  Tournament(int n) {
    for (offset = 1; offset < n; offset *= 2);
    tour.resize(2 * offset);
  }
  Node merge(Node lhs, Node rhs) {
    return Node(min(lhs.mini, rhs.mini), max(lhs.maks, rhs.maks), max(max(lhs.diff, rhs.diff), rhs.maks - lhs.mini), 0);
  }
  void prop(int x) {
    tour[x].mini += tour[x].lazy;
    tour[x].maks += tour[x].lazy;
    if (x < offset) {
      tour[2 * x].lazy += tour[x].lazy;
      tour[2 * x + 1].lazy += tour[x].lazy;
    }
    tour[x].lazy = 0;
  }
  void refresh(int x) {
    tour[x] = merge(tour[2 * x], tour[2 * x + 1]);
  }
  void update(int x, int lo, int hi, int from, int to, int val) {
    prop(x);
    if (lo >= to || hi <= from)
      return;
    if (lo >= from && hi <= to) {
      tour[x].lazy += val;
      prop(x);
      return;
    }
    int mid = (lo + hi) / 2;
    update(2 * x, lo, mid, from, to, val);
    update(2 * x + 1, mid, hi, from, to, val);
    refresh(x);
  }
  void update(int x, int val) {
    update(1, 0, offset, x, offset, val);
  }
  void modify(int x, int lo, int hi, int pos, int val) {
    prop(x);
    if (lo > pos || hi <= pos)
      return;
    if (hi - lo == 1) {
      tour[x].mini += val - INF;
      tour[x].maks += val + INF;
      return;
    }
    int mid = (lo + hi) / 2;
    modify(2 * x, lo, mid, pos, val);
    modify(2 * x + 1, mid, hi, pos, val);
    refresh(x);
  }
  void modify(int x, int val) {
    modify(1, 0, offset, x, val);
  }
  ll get() {
    prop(1);
    return max(tour[1].diff, 0ll);
  }
};

int N, M, D;
int pos[MAXN];
pii p[MAXN];

void load() {
  scanf("%d%d%d", &N, &M, &D);
  for (int i = 0; i < N + M; i++) {
    scanf("%d", &p[i].first);
    p[i].second = i;
  }
}

void solve() {
  sort(p, p + N + M);
  for (int i = 0; i < N + M; i++)
    pos[p[i].second] = i;
  Tournament solver(N + M);
  for (int i = 0; i < N + M; i++) {
    solver.modify(pos[i], -p[pos[i]].first);
    solver.update(pos[i], D);
    ll ans = solver.get();
    if (i >= N)
      printf("%lld%s", ans / 2, ans % 2 ? ".5 " : " ");
  }
  puts("");
}

int main() {
  load();
  solve();
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void load()':
Main.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d%d", &N, &M, &D);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d", &p[i].first);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41