Submission #255145

#	Time	Username	Problem	Language	Result	Execution time	Memory
255145		fedoseevtimofey	Arranging Tickets (JOI17_arranging_tickets)	C++14	65 / 100	6035 ms	17996 KiB

arranging_tickets

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int Inf = 1e9;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  vector <int> a(m), b(m), c(m);
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i] >> c[i];
    --a[i], --b[i];
    if (a[i] > b[i]) swap(a[i], b[i]);
  }
  vector <int> cnt(n);
  for (int i = 0; i < m; ++i) {
    ++cnt[a[i]];
    --cnt[b[i]];
  }
  vector <vector <int>> who(n);
  for (int i = 0; i < m; ++i) {
    who[a[i]].push_back(b[i]);
  }
  for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
  vector <int> need(2 * m + 1, Inf);
  for (int delta = -m; delta <= m; ++delta) {
    vector <int> cur = cnt;
    for (int i = 0; i < n; ++i) {
      cur[i] += delta;
      cur[i] = max(cur[i], 0);
      cur[i] = (cur[i] + 1) / 2;
    }
    int cnt_open = 0;
    vector <int> close(n);
    multiset <int> have;
    int cnt_need = 0;
    for (int i = 0; i < n; ++i) {
      cnt_open -= close[i]; 
      cur[i] -= cnt_open; 
      for (auto r : who[i]) have.insert(r);
      while (cur[i] > 0) {
        if (have.empty()) {
          break;
        }
        ++cnt_need;
        ++cnt_open;
        --cur[i];
        ++close[*have.rbegin()];
        have.erase(--have.end());
      }
      if (cur[i] > 0) {
        cnt_need = Inf;
        break;
      }
    }
    need[delta + m] = cnt_need;
  }
  int low = 0, high = m;
  while (high - low > 1) {
    int mid = (low + high) >> 1;
    bool good = false;
    for (int cnt_go = 0; cnt_go <= m; ++cnt_go) {
      int all_delta = cnt_go - mid;
      if (need[all_delta + m] <= cnt_go) {
        good = true; 
      }
    }
    if (good) high = mid;
    else low = mid;
  }
  cout << high << '\n';
}

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