제출 #1277168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277168		behrad	Arranging Tickets (JOI17_arranging_tickets)	C++17	65 / 100	5991 ms	5360 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, m, l[maxn], r[maxn], add[maxn], a[maxn];
vector<int> E[maxn];
multiset<int> st;

inline bool chk(int p, int x, int r) {
  if (r > x || r < 0) return 0;
  st.clear();
  fill(add, add + n + 1, 0);
  int cnt = 0;
  for (int i = 1 ; i <= p ; i ++) {
    int need = (a[i] - x + r + 1) / 2;
    for (int j : E[i]) if (j >= p) st.insert(j);
    while (cnt < need) {
      if (st.empty()) return 0;
      ++ cnt;
      auto R = prev(st.end());
      add[0] ++;
      add[i] -= 2;
      add[*R + 1] += 2;
      st.erase(R);
    }
  }
  for (int i = 0 ; i <= n - 1 ; i ++) {
    if (i >= 1) add[i] += add[i - 1];
    if (a[i] + add[i] > x) return 0;
  }
  return 1;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> m;
  if (n > 3000 || m > 3000) return 0;
  for (int i = 1, c ; i <= m ; i ++) {
    cin >> l[i] >> r[i] >> c;
    if (c != 1) return 0;
    if (l[i] > r[i]) swap(l[i], r[i]);
    a[l[i]] += c;
    a[r[i]] -= c;
    E[l[i]].pb(r[i] - 1);
  }
  for (int i = 1 ; i <= n ; i ++) a[i] += a[i - 1];

  int ans = m;
  for (int p = 1 ; p <= n-1 ; p ++) {
    int l = 0, r = a[p] + 1;
    while (r - l > 1) {
      int mid = (l + r) >> 1;
      if (chk(p, mid, a[p] - mid) || chk(p, mid, a[p] - mid + 1)) r = mid;
      else l = mid;
    }
    if (r != a[p] + 1) ans = min(ans, r);
  }
  cout << ans << nl;
}

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