Submission #232839

#	Time	Username	Problem	Language	Result	Execution time	Memory
232839		AlexLuchianov	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	5 ms	384 KiB

arranging_tickets

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

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
ll const inf = 1000000000000000000;

struct Person{
  int x;
  int y;
  int cost;
  bool operator < (Person const &a) const {
    return y < a.y;
  }
} v[1 + nmax];

class SegmentTree{
private:
  vector<ll> aint;
  vector<ll> lazy;
public:
  SegmentTree(int n){
    aint.resize(1 + 4 * n);
    lazy.resize(1 + 4 * n);
  }
  void cleannode(int node, int from, int to){
    if(lazy[node] == 0)
      return ;
    if(from < to){
      int mid = (from + to) / 2;
      lazy[node * 2] += lazy[node];
      lazy[node * 2  + 1] += lazy[node];
    }
    aint[node] += lazy[node];
    lazy[node] = 0;
  }

  void computenode(int node, int from, int to){
    aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
  }

  void update(int node, int from, int to, int x, int y, ll val){
    if(from == x && to == y){
      lazy[node] += val;
      cleannode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);

      if(x <= mid)
        update(node * 2, from, mid, x, MIN(y, mid), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }

  int query(int node, int from, int to, int x, int y){
    cleannode(node, from, to);

    if(from == x && to == y)
      return aint[node];
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, mid + 1, y);
      else
        return max(query(node * 2, from, mid, x, mid), query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
};

int eval(int n, int q, ll target){
  SegmentTree aint(n);
  ll result = 0;
  for(int i = 1;i <= q; i++){
    ll acc = min((target - aint.query(1, 1, n, v[i].x, v[i].y - 1)), 1LL * v[i].cost);
    result += v[i].cost - acc;
    aint.update(1, 1, n, v[i].x, v[i].y - 1, acc);
  }
  return (result <= target);
}

int binarysearch(ll from, ll to, int n, int q){
  if(from < to){
    ll mid = (from + to) / 2;
    if(eval(n, q, mid) == 1)
      return binarysearch(from, mid, n, q);
    else
      return binarysearch(mid + 1, to, n, q);
  } else
    return from;
}

int main()
{
  int n, q;
  cin >> n >> q;
  for(int i = 1;i <= q; i++){
    cin >> v[i].x >> v[i].y >> v[i].cost;
    if(v[i].y < v[i].x)
      swap(v[i].x, v[i].y);
  }
  sort(v + 1, v + q + 1);
  cout << binarysearch(1, inf, n, q);
  return 0;
}

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