Submission #1270928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270928		cpismylifeOwO	별자리 3 (JOI20_constellation3)	C++20	100 / 100	670 ms	361832 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;

struct Star
{
    int x, y, a, b;
    long long c;
};

int n, m;
int arr[MaxN];
Star add[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
        arr[x] = n - arr[x];
    }
    cin >> m;
    for (int x = 1; x <= m; x++)
    {
        cin >> add[x].x >> add[x].y >> add[x].c;
        add[x].y = n - add[x].y + 1;
    }
}

int root;
pair<int, int> graph[MaxN];

void BuildTree()
{
    for (int x = 1; x <= n; x++)
    {
        graph[x] = make_pair(-1, -1);
    }
    stack<int> st;
    for (int x = 1; x <= n; x++)
    {
        int pre = -1;
        while (!st.empty() && arr[st.top()] >= arr[x])
        {
            pre = st.top();
            st.pop();
        }
        if (st.empty())
        {
            graph[x].first = pre;
            root = x;
        }
        else
        {
            graph[x].first = pre;
            graph[st.top()].second = x;
        }
        st.push(x);
    }
}

int par[MaxN];
int h[MaxN];

void PreDFS(int u)
{
    if (graph[u].first != -1)
    {
        h[graph[u].first] = h[u] + 1;
        par[graph[u].first] = u;
        PreDFS(graph[u].first);
    }
    if (graph[u].second != -1)
    {
        h[graph[u].second] = h[u] + 1;
        par[graph[u].second] = u;
        PreDFS(graph[u].second);
    }
}

int BinLift[MaxLog][MaxN];

void Build()
{
    for (int x = 1; x <= n; x++)
    {
        BinLift[0][x] = par[x];
    }
    for (int x = 1; x < MaxLog; x++)
    {
        for (int y = 1; y <= n; y++)
        {
            BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
        }
    }
}

struct Node
{
    int lc, rc, l, r;
    long long res, lazyadd, lazymx;

    Node(int _l = 0, int _r = 0, long long _res = 0)
    {
        l = _l;
        r = _r;
        lc = rc = -1;
        res = _res;
        lazyadd =  0;
        lazymx = -inf;
    }
};

int curPos;
Node SegTree[8 * MaxN];

void Fix(int pos)
{
    Node& p = SegTree[pos];
    if (p.lazyadd == 0 && p.lazymx == -inf)
    {
        return;
    }
    p.res = max(p.res, p.lazymx) + p.lazyadd;
    if (p.lc != -1)
    {
        SegTree[p.lc].lazymx = max(SegTree[p.lc].lazymx, p.lazymx - SegTree[p.lc].lazyadd);
        SegTree[p.lc].lazyadd += p.lazyadd;
    }
    if (p.rc != -1)
    {
        SegTree[p.rc].lazymx = max(SegTree[p.rc].lazymx, p.lazymx - SegTree[p.rc].lazyadd);
        SegTree[p.rc].lazyadd += p.lazyadd;
    }
    p.lazyadd = 0;
    p.lazymx = -inf;
}

void MakeChild(int pos)
{
    Fix(pos);
    Node& p = SegTree[pos];
    int l = p.l, r = p.r;
    if (l == r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    if (p.lc == -1)
    {
        curPos++;
        SegTree[curPos] = Node(l, mid, p.res);
        p.lc = curPos;
    }
    if (p.rc == -1)
    {
        curPos++;
        SegTree[curPos] = Node(mid + 1, r, p.res);
        p.rc = curPos;
    }
}

void UpdateAdd(int pos, int i, int j, long long u)
{
    Fix(pos);
    Node& p = SegTree[pos];
    int l = p.l, r = p.r;
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        p.lazyadd += u;
        Fix(pos);
        return;
    }
    MakeChild(pos);
    UpdateAdd(p.lc, i, j, u);
    UpdateAdd(p.rc, i, j, u);
    p.res = max(SegTree[p.lc].res, SegTree[p.rc].res);
}

void UpdateMx(int pos, int i, int j, long long u)
{
    Fix(pos);
    Node& p = SegTree[pos];
    int l = p.l, r = p.r;
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        p.lazymx = max(p.lazymx, u - p.lazyadd);
        Fix(pos);
        return;
    }
    MakeChild(pos);
    UpdateMx(p.lc, i, j, u);
    UpdateMx(p.rc, i, j, u);
    p.res = max(SegTree[p.lc].res, SegTree[p.rc].res);
}

long long Get(int pos, int i, int j)
{
    Fix(pos);
    Node& p = SegTree[pos];
    int l = p.l, r = p.r;
    if (j < l || r < i)
    {
        return 0;
    }
    if (i <= l && r <= j)
    {
        return p.res;
    }
    MakeChild(pos);
    return max(Get(p.lc, i, j), Get(p.rc, i, j));
}

int Merge(int pos1, int pos2)
{
    Fix(pos1);
    Fix(pos2);
    Node& p = SegTree[pos1];
    Node& q = SegTree[pos2];
    if (p.lc == -1 && p.rc == -1)
    {
        q.lazymx = max(q.lazymx, p.res - q.lazyadd);
        Fix(pos2);
        return pos2;
    }
    if (q.lc == -1 && q.rc == -1)
    {
        p.lazymx = max(p.lazymx, q.res - p.lazyadd);
        Fix(pos1);
        return pos1;
    }
    p.lc = Merge(p.lc, q.lc);
    p.rc = Merge(p.rc, q.rc);
    p.res = max(SegTree[p.lc].res, SegTree[p.rc].res);
    return pos1;
}

int curST[MaxN];
vector<int> mark[MaxN];
long long F[MaxN];

void DFS(int u)
{
    curPos++;
    SegTree[curPos] = Node(1, n, 0);
    curST[u] = curPos;
    long long s = 0;
    if (graph[u].first != -1)
    {
        DFS(graph[u].first);
        s += F[graph[u].first];
    }
    if (graph[u].second != -1)
    {
        DFS(graph[u].second);
        s += F[graph[u].second];
    }
    if (graph[u].first != -1 && graph[u].second != -1)
    {
        UpdateAdd(curST[graph[u].first], 1, n, F[graph[u].second]);
        UpdateAdd(curST[graph[u].second], 1, n, F[graph[u].first]);
    }
    if (graph[u].first != -1)
    {
        curST[u] = Merge(curST[u], curST[graph[u].first]);
    }
    if (graph[u].second != -1)
    {
        curST[u] = Merge(curST[u], curST[graph[u].second]);
    }
    for (int x : mark[u])
    {
        //cout << u << " " << add[x].b << " " << add[x].c << "\n";
        UpdateMx(curST[u], 1, h[add[x].b], s + add[x].c);
    }
    F[u] = Get(curST[u], h[u], n);
    //cout << Get(curST[u], 1, 1) << ":" << u << ":" << F[u] << "\n";
}

void Exc()
{
    BuildTree();
    h[root] = 1;
    PreDFS(root);
    Build();
    long long res = 0;
    for (int x = 1; x <= m; x++)
    {
        add[x].a = add[x].x;
        add[x].b = add[x].x;
        for (int y = MaxLog - 1; y >= 0; y--)
        {
            if (arr[BinLift[y][add[x].b]] >= add[x].y)
            {
                add[x].b = BinLift[y][add[x].b];
            }
        }
        mark[add[x].a].push_back(x);
        res += add[x].c;
    }
    DFS(root);
    cout << res - F[root];
}

int main()
{
    //freopen("D.INP", "r", stdin);
    //freopen("D.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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