Submission #231352

#	Time	Username	Problem	Language	Result	Execution time	Memory
231352		AlexLuchianov	Pinball (JOI14_pinball)	C++14	100 / 100	630 ms	94712 KiB

pinball

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

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

int const nmax = 100000;
ll const inf = 1LL * 1000000000 * nmax * 10;

class SegmentTree{
private:
  struct Node{
    ll number;
    Node* left;
    Node* right;
    Node(ll val){
      number = val;
      left = right = nullptr;
    }
  };
  Node* root = nullptr;

  void computenode(Node* &root){
    if(root->left == nullptr && root->right == nullptr)
      root->number = inf;
    else if(root->left == nullptr)
      root->number = root->right->number;
    else if(root->right == nullptr)
      root->number = root->left->number;
    else
      root->number = std::min(root->left->number, root->right->number);
  }

  void _update(Node* &root, int from, int to, int x, ll val){
    if(root == nullptr)
      root = new Node(val);

    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        _update(root->left, from, mid, x, val);
      else if(mid + 1 <= x)
        _update(root->right, mid + 1, to, x, val);
      computenode(root);
    } else
      root->number = std::min(root->number, val);
  }

  ll _query(Node* &root, int from, int to, int x, int y){
    if(root == nullptr)
      return inf;
    if(from == x && to == y)
      return root->number;
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return _query(root->left, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return _query(root->right, mid + 1, to, x, y);
      else
        return std::min(_query(root->left, from, mid, x, mid), _query(root->right, mid + 1, to, mid + 1, y));
    }
  }
public:
  void update(int from, int to, int x, ll val){
    _update(root, from, to, x, val);
  }
  ll query(int from, int to, int x, int y){
    return _query(root, from, to, x, y);
  }
};

int main()
{
  int n, lim;
  std::cin >> n >> lim;
  SegmentTree aint1, aint2;

  aint1.update(1, lim, 1, 0);
  aint2.update(1, lim, lim, 0);


  ll result = inf;
  for(int i = 1;i <= n; i++){
    int from, mid, to, cost;
    std::cin >> from >> to >> mid >> cost;
    ll result1 = aint1.query(1, lim, from, to);
    ll result2 = aint2.query(1, lim, from, to);

    aint1.update(1, lim, mid, result1 + cost);
    aint2.update(1, lim, mid, result2 + cost);

    result = std::min(result, result1 + result2 + cost);
  }
  if(result == inf)
    std::cout << -1;
  else
    std::cout << result;
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49