oj.uz

Submission #371168

# Submission time Handle Problem Language Result Execution time Memory
371168 2021-02-26T03:04:58 Z 12tqian Treatment Project (JOI20_treatment) C++17
0 / 100
 59 ms 8808 KB 
#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 1e5 + 5;
const int L = 20;
const ll INF = 1e18;

int n, m, t[N], l[N], r[N], c[N], pos[N];

vpi v;

struct Node {
    ll val;
    int v;
    Node() {}
    Node(ll val, int v) : val(val), v(v) {}
    Node operator + (const Node& A) { // set min
        if (val <= A.val) return *this;
        return A;
    }
} st[(1 << L)];

void pull(int ind) {
    st[ind] = st[2 * ind] + st[2 * ind + 1];
}

void upd(int id, Node A, int ind = 1, int l = 0, int r = (1 << L) - 1) {
    if (id < l || id > r) return;
    if (l == r) { 
        st[ind] = A;
        return;
    }
    int m = (l + r) >> 1;
    upd(id, A, 2 * ind, l, m);
    upd(id, A, 2 * ind + 1, m + 1, r);
    pull(ind);
}

Node query(int lo, int hi, int ind = 1, int l = 0, int r = (1 << L) - 1) {
    if (r < lo || hi < l) return Node(INF, -1);
    if (lo <= l && r <= hi) return st[ind];
    int m = (l + r) >> 1;
    return query(lo, hi, 2 * ind, l, m) + query(lo, hi, 2 * ind + 1, m + 1, r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> m >> n;
    f0r(i, n) {
        cin >> t[i] >> l[i] >> r[i] >> c[i];
        l[i]--;
        v.eb(l[i] + t[i], i);
    }
    sort(all(v)); // sorted by order of l[i] + t[i]
    f0r(i, n) {
        int id = v[i].s;
        pos[id] = i; // reverse the id position
        upd(i, Node(l[id] - t[id], id)); // update with that at loc
    }
    priority_queue<pl, vpl, greater<pl>> pq;
    f0r(i, n) {
        if (l[i] == 0) {
            pq.emplace(c[i], i); // src nodes
            upd(pos[i], Node(INF, i));
        }
    }
    ll ans = INF;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int i = cur.s;
        ll w = cur.f;
        if (r[i] == m) { // reached end
            ckmin(ans, w);
        }
        int y = upper_bound(all(v), mp(r[i] + t[i], m - 1)) - v.begin() - 1;
        while (true) {
            Node x = query(0, y);
            if (x.val <= r[i] - t[i]) {
                pq.emplace(w + c[x.v], x.v);
                upd(pos[x.v], Node(INF, -1));
            } else break;
        }
    }
    if (ans == INF) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 8808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 8808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -