Submission #533565

#	Time	Username	Problem	Language	Result	Execution time	Memory
533565		cadmiumsky	Pinball (JOI14_pinball)	C++14	100 / 100	667 ms	42528 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define int ll
int n, m;
const ll inf = 1e17 + 5;
const int nmax = 3e5 + 33;
#define left deobiceicineintreabasussy
#define right deobiceicineintreababaka
struct AINT {
  ll tree[4 * nmax];
  ll query(int l, int r, int node = 1, int cl = 1, int cr = n) {
    //cout << l << ' ' << r << '\t' << cl << ' ' << cr << ' ' << tree[node] << '\n';
    if(r < cl || cr < l)
      return inf;
    if(l <= cl && cr <= r)
      return tree[node];
    int mid = cl + cr >> 1;
    return min(query(l, r, 2 * node, cl, mid), query(l, r, 2 * node + 1, mid + 1, cr));
  }
  void upd(int poz, ll val, int node = 1, int cl = 1, int cr = n) {
    if(cl == cr) {
      tree[node] = min(tree[node], val);
      return;
    }
    int mid = cl + cr >> 1;
    if(poz <= mid) upd(poz, val, 2 * node, cl, mid);
    else upd(poz, val, 2 * node + 1, mid + 1, cr);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
  } // asta nu se numeste smenul lui nicu
  void construct(int node = 1, int cl = 1, int cr = n) {
    tree[node] = inf;
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    construct(2 * node, cl, mid);
    construct(2 * node + 1, mid + 1, cr);
  }
};
AINT left, right;

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

signed main() {
  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;
  left.construct();
  right.construct();
  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 member function 'long long int AINT::query(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:18:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
pinball.cpp: In member function 'void AINT::upd(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:26:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
pinball.cpp: In member function 'void AINT::construct(long long int, long long int, long long int)':
pinball.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
pinball.cpp: In function 'int main()':
pinball.cpp:48:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |   for(auto &[a, b, c, d] : v) {
      |             ^
pinball.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   for(auto [a, b, c, d] : v) {
      |            ^

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