Submission #514868

#	Time	Username	Problem	Language	Result	Execution time	Memory
514868		600Mihnea	Robots (IOI13_robots)	C++17	100 / 100	2958 ms	36332 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e6 + 7;
const int L = 50000 + 7;
const ll INF = (ll) 1e18 + 7;
int cover1[N];
int cover2[N];
vector<int> la[L];
int sz1;
int sz2;

ll tree[4 * L];
ll lazy[4 * L];

void clr() {
  for (int i = 0; i < 4 * L; i++) {
    lazy[i] = 0;
    tree[i] = 0;
  }
}

void push(int v, int tl, int tr) {
  if (lazy[v]) {
    tree[v] += lazy[v];
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    lazy[v] = 0;
  }
}

void add(int v, int tl, int tr, int l, int r, ll x) {
  push(v, tl, tr);
  if (tr < l || r < tl) return;
  if (l <= tl && tr <= r) {
    lazy[v] += x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  add(2 * v, tl, tm, l, r, x);
  add(2 * v + 1, tm + 1, tr, l, r, x);
  tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

void add(int l, int r, ll x) {
  add(1, 0, sz2, l, r, x);
}

bool isok(int k) {
  /// (i + j) * k >= cnt[i][j]
  /// la un i anumit imi pasa de i * k >= cnt[i][j] - j * k
  /// cnt[i][j] - j * k trebuie sa fie maxim

  clr();

  for (int j = 0; j <= sz2; j++) {
    add(j, j, -(j * (ll) k));
  }

  for (int i = 0; i <= sz1; i++) {
    for (auto &j : la[i]) {
      add(j, sz2, +1);
    }

    bool ok = (i * (ll) k >= tree[1]);
    if (!ok) {
      return 0;
    }
  }
  return 1;
}

int putaway(int __sz1, int __sz2, int n, int val1[], int val2[], int x[], int y[]) {
  sz1 = __sz1;
  sz2 = __sz2;
  assert(sz1 < L);
  assert(sz2 < L);
  vector<pair<int, int>> xx, yy;
  for (int i = 0; i < n; i++) {
    xx.push_back({x[i], i});
    yy.push_back({y[i], i});
    cover1[i] = -1;
    cover2[i] = -1;
  }
  sort(xx.rbegin(), xx.rend());
  sort(yy.rbegin(), yy.rend());

  for (int i = 0; i < sz1; i++) {
    val1[i]--;
  }
  for (int i = 0; i < sz2; i++) {
    val2[i]--;
  }
  sort(val1, val1 + sz1); reverse(val1, val1 + sz1);
  sort(val2, val2 + sz2); reverse(val2, val2 + sz2);
  {
    int p1 = 0;
    for (auto &it : xx) {
      while (p1 < sz1 && it.first <= val1[p1]) p1++;
      cover1[it.second] = p1;
    }
  }
  {
    int p2 = 0;
    for (auto &it : yy) {
      while (p2 < sz2 && it.first <= val2[p2]) p2++;
      cover2[it.second] = p2;
    }
  }
  for (int i = 0; i < n; i++) {
    assert(0 <= cover1[i] && cover1[i] <= sz1);
    assert(0 <= cover2[i] && cover2[i] <= sz2);
    la[cover1[i]].push_back(cover2[i]);
  }
  int low = 1, high = n, sol = -1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (isok(mid)) {
      sol = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return sol;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10