Submission #1138381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138381		OI_Account	치료 계획 (JOI20_treatment)	C++20	0 / 100	101 ms	21432 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 400'000;
const ll INF = 1'000'000'000'000'000'000;

int n, m, t[N + 10], l[N + 10], r[N + 10], c[N + 10];
ll seg[4 * N + 10], lazy[4 * N + 10];
int x;
vector<int> en[N + 10];
vector<int> vec;

void readInput() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> t[i] >> l[i] >> r[i] >> c[i];
}

bool isSub1() {
    return *max_element(t + 1, t + m + 1) == 1;
}

ll get(int idx, int id = 1, int l = 0, int r = x) {
    if (idx < l || r <= idx)
        return INF;
    if (l + 1 == r)
        return lazy[id];
    int mid = (l + r) >> 1;
    return min({lazy[id], get(idx, id << 1, l, mid), get(idx, id << 1 | 1, mid, r)});
}

void update(int st, int en, ll val, int id = 1, int l = 0, int r = x) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        lazy[id] = min(lazy[id], val);
        return;
    }
    int mid = (l + r) >> 1;
    update(st, en, val, id << 1, l, mid);
    update(st, en, val, id << 1 | 1, mid, r);
}

void build(int id = 1, int l = 0, int r = x) {
    for (int i = 1; i <= 4 * x + 5; i++)
        lazy[i] = INF;
}

int getIdx(int x) {
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

void init() {
    vec = {0, n};
    for (int i = 1; i <= m; i++) {
        vec.push_back(l[i]);
        vec.push_back(r[i]);
    }
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    for (int i = 1; i <= m; i++) {
        l[i] = getIdx(l[i]);
        r[i] = getIdx(r[i]);
        en[r[i]].push_back(i);
    }
    x = vec.size();
}

void solveSub1() {
    init();
    build();
    update(0, 1, 0);
    for (int i = 1; i < x; i++) {
        for (auto idx: en[i]) {
            ll tmp = get(l[idx] - 1);
            update(l[idx], i + 1, tmp + c[idx]);
        }
    }
    cout << get(x - 1) << flush;
}

void solveSub2() {

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    if (isSub1())
        solveSub1();
    else if (m <= 16)
        solveSub2();
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61