oj.uz

Submission #533545

# Submission time Handle Problem Language Result Execution time Memory
533545 2022-03-06T09:11:46 Z cadmiumsky Pinball (JOI14_pinball) C++14
11 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n, m;
const ll inf = 1e16 + 5;
const int nmax = 3e5 + 2;
#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) {
    tree[node] = min(tree[node], val);
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    if(poz <= mid)
      return upd(poz, val, 2 * node, cl, mid);
    return upd(poz, val, 2 * node + 1, mid + 1, cr);
  } // asta 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;

int main() {
  cin >> m >> n;
  vector<tuple<int,int,int,int> > 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;
  for(auto [a, b, c, d] : v) {
    a = norm[a];
    b = norm[b];
    c = norm[c];
    ll l = left.query(a, c), r = right.query(c, b);
    //cout << l << ' ' << r << '\n';
    minn = min(minn, l + r + d);
    left.upd(c, l + d);
    right.upd(c, r + d);
  }
  if(minn >= 1e16 + 1)
    cout << -1 << '\n';
  else
    cout << minn << '\n';
}

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -