Submission #533576

#	Time	Username	Problem	Language	Result	Execution time	Memory
533576		cadmiumsky	Pinball (JOI14_pinball)	C++14	51 / 100	1049 ms	31508 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
const ll inf = 1e17 + 5;
const int nmax = 3e5 + 33;
#define left deobiceicineintreabasussy
#define right deobiceicineintreababaka

mt19937 rng(time(0));

struct Treap {
  struct node {
    int pri;
    ll mn, val;
    int area;
    node *l, *r;
    int ind() {
      return l -> area + 1;
    }
  } *nil = new node{-1, inf, inf, 0, 0, 0};
  using ns = node*;
  struct pns {
    ns l, r;
  };
  ns updnode(ns nde, ns x, int val) {
    (val? nde -> r : nde -> l) = x;
    nde -> area = nde -> l -> area + nde -> r -> area + 1;
    nde -> mn = min({nde -> l -> mn, nde -> r -> mn, nde -> val});
    return nde;  
  }
  ns merge(ns l, ns r) {
    return l == nil? r:
            r == nil? l:
              l -> pri > r -> pri? updnode(l, merge(l -> r, r), 1):
                updnode(r, merge(l, r -> l), 0);
  }
  pns split(ns x, int val) {
    pns temp;
    return val == 0? pns{nil, x}:
            x -> area <= val? pns{x, nil}:
              x -> ind() <= val? (temp = split(x -> r, val - x -> ind()), temp.l = updnode(x, temp.l, 1), temp):
                (temp = split(x -> l, val), temp.r = updnode(x, temp.r, 0), temp);
  }
  ns root = nil;
  void append() {
    root = merge(root, new node{abs((int)rng()), inf, inf, 1, nil, nil});
  }
  ll query(int l, int r) {
    pns temp[2] = {split(root, l - 1), split(temp[0].r, r - l + 1)};
    ll rez = temp[1].l -> mn;
    root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
    return rez;
  }
  void upd(int poz, ll val) {
    pns temp[2] = {split(root, poz - 1), split(temp[0].r, 1)};
    temp[1].l -> val = min(temp[1].l -> val, val);
    temp[1].l -> mn = temp[1].l -> val;
    root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
    return;
  }
};
Treap left, right;

#define norm deobiceicineintreaba
map<int,int> norm;

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> m >> n;
  vector<tuple<int,int,int,ll> > v(m);
  for(auto &[a, b, c, d] : v) {
    cin >> a >> b >> c >> d;
    norm[a];
    norm[b];
    norm[c];
  }
  norm[1];
  norm[n];
  int cnt = 1;
  for(auto &x : norm)
    x.second = cnt++;
  n = cnt - 1;
  for(int i = 1; i <= n; i++) {
    left.append();
    right.append();
  }
  left.upd(1, 0);
  right.upd(n, 0);
  ll minn = inf;
  bool ok = 0;
  for(auto [a, b, c, d] : v) {
    a = norm[a];
    b = norm[b];
    c = norm[c];
    ll l = left.query(a, b), r = right.query(a, b);
    //cout << l << ' ' << r << '\n';
    if(minn > l + r + d)
      minn = l + r + d, ok = 1;
    left.upd(c, l + d);
    right.upd(c, r + d);
  }
  if(!ok)
    cout << -1 << '\n';
  else
    cout << minn << '\n';
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:73:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |   for(auto &[a, b, c, d] : v) {
      |             ^
pinball.cpp:93:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |   for(auto [a, b, c, d] : v) {
      |            ^

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