Submission #700950

#	Time	Username	Problem	Language	Result	Execution time	Memory
700950		Farbod	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	520 ms	524288 KiB

constellation3

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Sun, 19 Feb 2023 (16:42:59)
*
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const long long inf = 1e18;

int pw[N];

int n, m, a[N], dp[N][20];
long long s[N], Ans = inf;
vector <pair <int, int>> adj[N];

vector <int> v;

int mx(int l, int r)
{
    if (a[dp[l][pw[r - l + 1]]] > a[dp[r - (1 << pw[r - l + 1]) + 1][pw[r - l + 1]]])
        return dp[l][pw[r - l + 1]];
    return dp[r - (1 << pw[r - l + 1]) + 1][pw[r - l + 1]];
}

int mn(int i, int x)
{
    int j = upper_bound(adj[i].begin(), adj[i].end(), make_pair(x + 1, 0)) - adj[i].begin();
    j--;

    if (j < 0)
        return 0;
    return adj[i][j].second;
}

void f(int l, int r, vector <long long> &ans)
{
    if (l > r) {
        for (int i = 0; i < (int)v.size(); i++)
            ans.push_back(0);
        v.pop_back();

        return;
    }
    if (l == r) {
        for (int i = 0; i < (int)v.size(); i++) 
            ans.push_back(s[l] - mn(l, v[i]));
        v.pop_back();

        return;
    }

    int mid = mx(l, r);

    vector <long long> ansL, ansR;
    v.push_back(a[mid]), f(l, mid - 1, ansL);
    v.push_back(a[mid]), f(mid + 1, r, ansR);

    for (int i = 0; i < (int)v.size(); i++) {
        Ans = inf;

        Ans = min(Ans, ansL[i] + ansR.back() + s[mid]),
        Ans = min(Ans, ansL.back() + ansR[i] + s[mid]),
        Ans = min(Ans, ansL.back() + ansR.back() + s[mid] - mn(mid, v[i]));

        ans.push_back(Ans);
    }

    //ansL.clear(), ansL.shrink_to_fit();
    //ansR.clear(), ansR.shrink_to_fit();

    v.pop_back();

    return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    pw[1] = 0;
    for (int i = 2; i < N; i++)
        pw[i] = pw[i / 2] + 1;

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i], dp[i][0] = i;

    for (int j = 1; j < 20; j++)
        for (int i = 0; i < n; i++) {
            if (a[dp[i][j - 1]] > a[dp[min(n - 1, i + (1 << (j - 1)))][j - 1]])
                dp[i][j] = dp[i][j - 1];
            else
                dp[i][j] = dp[min(n - 1, i + (1 << (j - 1)))][j - 1];
        }
                
    int x, y, c;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> c, x--;
        
        s[x] += c;
        adj[x].push_back({y, c});
    }

    for (int i = 0; i < n; i++) {
        sort(adj[i].begin(), adj[i].end());
        for (int j = 1; j < (int)adj[i].size(); j++)
            adj[i][j].second = max(adj[i][j].second, adj[i][j - 1].second);
    }

    vector <long long> ans;

    v.push_back(n), f(0, n - 1, ans);

    cout << ans.back();

    return 0;
}

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