Submission #582137

#	Time	Username	Problem	Language	Result	Execution time	Memory
582137		AlexLuchianov	Arranging Tickets (JOI17_arranging_tickets)	C++14	100 / 100	803 ms	13964 KiB

arranging_tickets

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <queue>

using ll = long long;

int const nmax = 200000;

ll acc[5 + nmax];
ll init[5 + nmax], pref[5 + nmax], suff[5 + nmax];
std::vector<std::pair<int,int>> queries[5 + nmax];

bool solve(int n, int m, int start, ll smax, ll target) {
  std::priority_queue<std::pair<int,int>> pq;
  for(int i = 1;i <= n; i++)
    acc[i] = 0;
  ll expended = 0;
  
  for(int i = 1;i <= start; i++) {
    ll needToErase = (1 + init[i] + target - smax) / 2;
    needToErase = std::max(0LL, needToErase - expended);
    for(int h = 0; h < queries[i].size(); h++)
      pq.push(queries[i][h]);
    expended += needToErase;
    
    while(0 < pq.size() && 0 < needToErase) {
      std::pair<int,int> tp = pq.top();
      pq.pop();
      if(needToErase < tp.second) {
        tp.second -= needToErase;
        pq.push(tp);
        acc[start] -= needToErase;
        acc[tp.first + 1] += 2 * needToErase;
        needToErase = 0;
      } else {
        acc[start] -= tp.second;
        acc[tp.first + 1] += 2 * tp.second;
        needToErase -= tp.second;
      }
    }
    if(0 < needToErase)
      return 0;
  }
  for(int i = 1; i <= n; i++)
    acc[i] += acc[i - 1];
  for(int i = start;i <= n; i++)
    if(!(acc[i] + init[i] <= smax))
      return 0;
  return 1;
};

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;
  for(int i = 1;i <= m; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    if(y < x)
      std::swap(x, y);
    y--;
    queries[x].push_back({y, cost});
    init[x] += cost;
    init[y + 1] -= cost;
  }
  for(int i = 2;i <= n; i++)
    init[i] += init[i - 1];
  int start = 1;
  for(int i = 1; i <= n; i++)
    if(init[start] < init[i])
      start = i;
  ll x = 0;
  
  for(ll jump = (1LL << 60); 0 < jump; jump /= 2)
    if(solve(n, m, start, init[start] - (x + jump), x + jump) == 1 || solve(n, m, start, init[start] - (x + jump), x + jump + 1))
      x += jump;
  std::cout << init[start] - x << '\n';
  return 0;
}

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