Submission #24098

#	Time	Username	Problem	Language	Result	Execution time	Memory
24098		jiaqiyang	Arranging Tickets (JOI17_arranging_tickets)	C++14	100 / 100	1376 ms	8152 KiB

arranging_tickets

#include <cstdio>
#include <algorithm>

const int N = 200000 + 10;

typedef long long i64;

int n, m;

struct Tuple {
  int x, y, z;
  Tuple() {}
  Tuple(int _x, int _y, int _z): x(_x), y(_y), z(_z) {}
  inline bool operator< (const Tuple &rhs) const {
    return x < rhs.x;
  }
} tuple[N];

i64 a[N];

bool solve(i64 cnt, i64 threshold) {
  cnt = std::min(cnt, threshold);
  static i64 b[N];
  std::fill(b + 1, b + n, 0);
  static std::pair<int, int> heap[N];
  i64 temp = cnt;
  int top = 0;
  for (int i = 1, j = 1; i < n; ++i) {
    b[i] += b[i - 1];
    for (; j <= m && tuple[j].x <= i; ++j) {
      heap[top++] = std::make_pair(tuple[j].y, tuple[j].z);
      std::push_heap(heap, heap + top);
    }
    i64 val = a[i] + cnt - 2 * b[i] - threshold;
    if (val <= 0) continue;
    i64 cur = (val + 1) / 2;
    while (top && cur && temp) {
      std::pop_heap(heap, heap + top);
      std::pair<int, int> &info = heap[--top];
      if (i >= info.first) continue;
      int det = std::min<i64>(info.second, std::min(cur, temp));
      info.second -= det;
      b[i] += det;
      b[info.first] -= det;
      cur -= det;
      temp -= det;
      if (info.second) std::push_heap(heap, heap + ++top);
    }
    if (cur) return false;
  }
  return true;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    if (x > y) std::swap(x, y);
    tuple[i] = Tuple(x, y, z);
    a[x] += z;
    a[y] -= z;
  }
  std::sort(tuple + 1, tuple + m + 1);
  for (int i = 1; i <= n; ++i) a[i] += a[i - 1];
  i64 l = 1, t = *std::max_element(a + 1, a + n), r = t;
  while (l < r) {
    i64 mid = (l + r) >> 1;
    if (solve(t - mid, mid) || solve(t - (mid - 1), mid)) r = mid; else l = mid + 1;
  }
  printf("%lld\n", l);
  return 0;
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
                        ^
arranging_tickets.cpp:58:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &x, &y, &z);
                                ^

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15