oj.uz

Submission #923490

# Submission time Handle Problem Language Result Execution time Memory
923490 2024-02-07T10:42:41 Z rolandpetrean Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = pair<int, int>;

const int INF = 1e16;

struct SegmentTree {
  int n;
  vector<int> data;
  
  void update(int u, int st, int dr, int p, int x) {
    if (st == dr) data[u] = x;
    else {
      int mid = (st + dr) / 2;
      if (p <= mid) update(2 * u, st, mid, p, x);
      else update(2 * u + 1, mid + 1, dr, p, x);
      data[u] = min(data[2 * u], data[2 * u + 1]);
    }
  }
  void update(int p, int x) {
    update(1, 1, n, p, x);
  }
  int query(int u, int st, int dr, int l, int r) {
    if (st >= l && dr <= r) return data[u];
    int mid = (st + dr) / 2, res = INF;
    if (l <= mid) res = query(2 * u, st, mid, l, r);
    if (mid < r) res = min(res, query(2 * u + 1, mid + 1, dr, l, r));
    return res;
  }
  int query(int l, int r) {
    return query(1, 1, n, l, r);
  }
  
  SegmentTree() {}
  SegmentTree(int n) {
    this->n = n;
    data.assign(4 * (n + 1), INF);
  }
};

struct Device {
  int a, b, c, d;
};

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int m, n;
  cin >> m >> n;
  
  vector<Device> d(m);
  for (int i = 0; i < m; ++i) cin >> d[i].a >> d[i].b >> d[i].c >> d[i].d;

  vector<int> vals{1};
  for (int i = 0; i < m; ++i) vals.insert(vals.end(), {d[i].a, d[i].b, d[i].c});
  vals.pb(n);
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  auto norm = [&](int x) {
    return upper_bound(vals.begin(), vals.end(), x) - vals.begin();
  };
  for (int i = 0; i < m; ++i) {
    d[i].a = norm(d[i].a);
    d[i].b = norm(d[i].b);
    d[i].c = norm(d[i].c);
  }
  n = vals.size();
  
  array<SegmentTree, 2> dp;
  dp[0] = SegmentTree(n);
  dp[1] = SegmentTree(n);
  dp[0].update(1, 0);
  dp[1].update(n, 0);
  
  int ans = INF;
  for (int i = 0; i < m; ++i) {
    int minl = dp[0].query(d[i].a, d[i].b), minr = dp[1].query(d[i].a, d[i].b);
    ans = min(ans, minl + minr + d[i].d);
    
    for (int j = 0; j <= 1; ++j) {
      int mini = dp[j].query(d[i].a, d[i].b);
      dp[j].update(d[i].c, mini + d[i].d);
    }
  }
  
  cout << (ans == INF ? -1 : ans) << endl;
}

/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -