Submission #1277583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277583		duckindog	Treatment Project (JOI20_treatment)	C++20	0 / 100	385 ms	542048 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m;
struct TREAT { 
    int t, l, r, c;
    friend istream& operator >> (istream& is, TREAT& rhs) { 
        return is >> rhs.t >> rhs.l >> rhs.r >> rhs.c;
    }
} treat[N];

vector<int> rrhT{0};

namespace IT { 
    bool mk[N];
    deque<int> f[N << 2], g[N << 2];
    void update(int s, int l, int r, int x, int y) { 
        if (x < l || x > r) return;
        f[s].push_back(y);
        g[s].push_back(y);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) update(s << 1, l, mid, x, y);
        else update(s << 1 | 1, mid + 1, r, x, y);
    }
    void build(int s, int l, int r) { 
        sort(f[s].begin(), f[s].end(), [&](const auto& i, const auto& j) { 
            return treat[i].l + rrhT[treat[i].t] > treat[j].l + rrhT[treat[j].t];
        });
        sort(g[s].begin(), g[s].end(), [&](const auto& i, const auto& j) { 
            return treat[i].l - rrhT[treat[i].t] > treat[j].l - rrhT[treat[j].t];
        });
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(s << 1, l, mid);
        build(s << 1 | 1, mid + 1, r);
    }

    vector<int> vt;
    void get1(int s, int l, int r, int u, int v, int x) { 
        if (v < l || u > r || !f[s].size()) return;
        if (u <= l && r <= v) { 
            for (; f[s].size(); f[s].pop_back()) { 
                int j = f[s].back(); 
                if (!mk[j]) { 
                    if (treat[j].l + rrhT[treat[j].t] > x) break;
                    vt.push_back(j);
                    mk[j] = true;
                }
            }
            return;
        }
        int mid = (l + r) >> 1;
        get1(s << 1, l, mid, u, v, x);
        get1(s << 1 | 1, mid + 1, r, u, v, x);
    }
    void get2(int s, int l, int r, int u, int v, int x) { 
        if (v < l || u > r || !g[s].size()) return;
        if (u <= l && r <= v) { 
            for (; g[s].size(); g[s].pop_back()) { 
                int j = g[s].back(); 
                if (!mk[j]) { 
                    if (treat[j].l - rrhT[treat[j].t] > x) break;
                    vt.push_back(j);
                    mk[j] = true;
                }
            }
            return;
        }
        int mid = (l + r) >> 1;
        get2(s << 1, l, mid, u, v, x);
        get2(s << 1 | 1, mid + 1, r, u, v, x);
    }
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> treat[i];

    for (int i = 1; i <= m; ++i) treat[i].l -= 1;

    for (int i = 1; i <= m; ++i) rrhT.push_back(treat[i].t);
    sort(rrhT.begin(), rrhT.end());
    rrhT.erase(unique(rrhT.begin(), rrhT.end()), rrhT.end());
    const int sz = rrhT.size() - 1;

    for (int i = 1; i <= m; ++i) { 
        auto& [t, l, r, c] = treat[i];
        t = lower_bound(rrhT.begin(), rrhT.end(), t) - rrhT.begin();
        IT::update(1, 1, sz, t, i);
    }
    IT::build(1, 1, sz);
    
    using pii = pair<long long, int>;
    priority_queue<pii, vector<pii>, greater<>> q;
    for (int i = 1; i <= m; ++i) { 
        if (!treat[i].l) { 
            IT::mk[i] = true;
            q.push({treat[i].c, i});
        }
    }

    while (q.size()) { 
        auto [d, u] = q.top(); q.pop();
        const auto& [t, l, r, c] = treat[u];
        
        if (r == n) { 
            cout << d << "\n";
            return 0;
        }

        IT::vt.clear();
        IT::get1(1, 1, sz, t, sz, r + rrhT[t]);
        IT::get2(1, 1, sz, 1, t, r - rrhT[t]);
        
        for (const auto& j : IT::vt) q.push({d + treat[j].c, j});
    }
    cout << -1 << "\n";
}

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