Submission #752174

#	Time	Username	Problem	Language	Result	Execution time	Memory
752174		puppy	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	362 ms	78644 KiB

constellation3

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <functional>
#define int long long
using namespace std;
int N, M;
int X[200005], Y[200005], L[200005], R[200005], A[200005];
long long C[200005];
vector<int> star[200005];
const int inf = 1e9;
struct Line
{
    int s, e;
    int X;
    long long c;
    bool operator<(const Line &ln)
    {
        if (s != ln.s) return s < ln.s;
        else return e > ln.e;
    }
};
Line ln[200005];
int par[200005];
vector<int> g[200005];
int indeg[200005];
long long dp[200005], sum[200005];
vector<int> ts;
int s[200005], e[200005], last[200005];
vector<int> llist[200005];
struct FenWick
{
    vector<long long> tree;
    int n;
    FenWick(int _n){n = _n; tree.resize(n+1);}
    void upd(int id, long long x)
    {
        for (;id<=n;id+=id&-id) tree[id] += x;
    }
    long long query(int id)
    {
        long long ans = 0;
        for (;id;id-=id&-id) ans += tree[id];
        return ans;
    }
};
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    cin >> M;
    for (int i = 1; i <= M; i++) {
        cin >> X[i] >> Y[i] >> C[i];
        star[X[i]].push_back(i);
    }
    priority_queue<pair<int, int>> pq;
    A[0] = A[N+1] = inf;
    for (int i = 1; i <= N + 1; i++) {
        while (!pq.empty() && -pq.top().first <= A[i]) {
            R[pq.top().second] = i;
            pq.pop();
        }
        for (int k:star[i]) pq.push(make_pair(-Y[k], k));
    }
    for (int i = N; i >= 0; i--) {
        while (!pq.empty() && -pq.top().first <= A[i]) {
            L[pq.top().second] = i;
            pq.pop();
        }
        for (int k:star[i]) pq.push(make_pair(-Y[k], k));
    }
    for (int i = 1; i <= M; i++) ln[i] = {L[i] + 1, R[i] - 1, X[i], C[i]};
    sort(ln + 1, ln + M + 1);
    for (int i = 1; i <= M; i++) llist[ln[i].s].push_back(i);
    priority_queue<int> pq2;
    for (int i = 1; i <= N; i++) {
        for (int k:llist[i]) pq2.push(k);
        while (!pq2.empty() && ln[pq2.top()].e < i) pq2.pop();
        if (!pq2.empty()) last[i] = pq2.top();
    }
    while (!pq2.empty()) pq2.pop();
    for (int i = 1; i <= M; i++) {
        while (!pq2.empty() && ln[pq2.top()].e < ln[i].s) pq2.pop();
        if (!pq2.empty()) {
            par[i] = pq2.top();
            g[par[i]].push_back(i);
        }
        pq2.push(i);
    }
    vector<int> root;
    for (int i = 1; i <= M; i++) {
        if (!par[i]) root.push_back(i);
    }
    int cur = 0;
    vector<int> ts;
    function<void(int)> dfs = [&](int v)
    {
        cur = v;
        s[v] = v;
        for (int i:g[v]) dfs(i);
        e[v] = cur;
        ts.push_back(v);
    };
    for (int i:root) dfs(i);
    FenWick fen(M);
    for (int i:ts) {
        int exc = last[ln[i].X];
        long long tmp1 = 0, tmp2 = 0;
        for (int j:g[i]) tmp1 += dp[j];
        for (int j:g[i]) {
            fen.upd(s[j], tmp1 - dp[j]);
            fen.upd(e[j] + 1, dp[j] - tmp1);
        }
        fen.upd(i, tmp1);
        fen.upd(i+1, -tmp1);
        tmp2 = ln[i].c + fen.query(exc);
        dp[i] = max(tmp1, tmp2);
    }
    long long ans = 0;
    for (int i = 1; i <= M; i++) ans += ln[i].c;
    for (int i:root) ans -= dp[i];
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65