Submission #582047

#	Time	Username	Problem	Language	Result	Execution time	Memory
582047		AlexLuchianov	Arranging Tickets (JOI17_arranging_tickets)	C++14	0 / 100	1 ms	320 KiB

arranging_tickets

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

using ll = long long;

class SegmentTree{
private:
  std::vector<ll> aint;
  std::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] = std::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, std::min(y, mid), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, std::max(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }

  ll query(int node, int from, int to, int x, int y){
    if(y < x)
      return 0;

    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, x, y);
      else
        return std::max(query(node * 2, from, mid, x, mid), query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
};

class Event{
public:
  int x;
  int y;
  int cost;
  ll prio;
  bool operator < (Event const oth) {
    return prio < oth.prio;
  }
};

int const nmax = 200000;

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

  int n, m;
  std::cin >> n >> m;
  std::vector<Event> queries;
  std::vector<ll> acc(1 + n), pref(1 + n), suff(1 + n);
  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.push_back({x, y, cost, 0}); 
    acc[x] += cost;
    acc[y + 1] -= cost;
  }
  for(int i = 2;i <= n; i++)
    acc[i] += acc[i - 1];
  for(int i = 1;i <= n; i++)
    pref[i] = suff[i] = acc[i];
  for(int i = 2;i <= n; i++)
    pref[i] = std::max(pref[i], pref[i - 1]);
  for(int i = n - 1; 1 <= i; i--)
    suff[i] = std::max(suff[i + 1], suff[i]);
  for(int i = 0; i < queries.size(); i++)
    queries[i].prio = std::max(pref[queries[i].x - 1], suff[queries[i].y + 1]);
  std::sort(queries.begin(), queries.end());
  SegmentTree aint(1 + n);
  for(int i = 0; i < queries.size(); i++) {
    aint.update(1, 1, n, queries[i].x, queries[i].y, queries[i].cost);
  }

  for(int i = 0; i < queries.size(); i++) {
    ll base = std::max(aint.query(1, 1, n, 1, queries[i].x - 1), aint.query(1, 1, n, queries[i].y + 1, n));
    ll internal = aint.query(1, 1, n, queries[i].x, queries[i].y);
    ll moves = std::min((internal - base) / 2, 1LL * queries[i].cost);
    if(moves < 0)
      break;
    aint.update(1, 1, n, 1, n, moves);
    aint.update(1, 1, n, queries[i].x, queries[i].y, -2 * moves);
  }
  std::cout << aint.query(1, 1, n, 1, n) << '\n';
  return 0;
}

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