oj.uz

Submission #533565

# Submission time Handle Problem Language Result Execution time Memory
533565 2022-03-06T09:59:07 Z cadmiumsky Pinball (JOI14_pinball) C++14
100 / 100
 667 ms 42528 KB 
#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

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.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 2 ms 304 KB Output is correct
17 Correct 5 ms 460 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 4 ms 588 KB Output is correct
20 Correct 3 ms 436 KB Output is correct
21 Correct 2 ms 440 KB Output is correct
22 Correct 4 ms 684 KB Output is correct
23 Correct 4 ms 588 KB Output is correct
24 Correct 3 ms 588 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 2 ms 304 KB Output is correct
17 Correct 5 ms 460 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 4 ms 588 KB Output is correct
20 Correct 3 ms 436 KB Output is correct
21 Correct 2 ms 440 KB Output is correct
22 Correct 4 ms 684 KB Output is correct
23 Correct 4 ms 588 KB Output is correct
24 Correct 3 ms 588 KB Output is correct
25 Correct 31 ms 3020 KB Output is correct
26 Correct 96 ms 7500 KB Output is correct
27 Correct 393 ms 15472 KB Output is correct
28 Correct 240 ms 7468 KB Output is correct
29 Correct 248 ms 13516 KB Output is correct
30 Correct 311 ms 9376 KB Output is correct
31 Correct 591 ms 26040 KB Output is correct
32 Correct 605 ms 19016 KB Output is correct
33 Correct 63 ms 7216 KB Output is correct
34 Correct 245 ms 21272 KB Output is correct
35 Correct 336 ms 42420 KB Output is correct
36 Correct 667 ms 42528 KB Output is correct
37 Correct 621 ms 42500 KB Output is correct
38 Correct 498 ms 42436 KB Output is correct