Submission #851304

#	Time	Username	Problem	Language	Result	Execution time	Memory
851304		danikoynov	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	3 ms	14936 KiB

constellation3

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct point
{
    int x, y, c;
    bool operator < (const point &p) const
    {
        if (x == p.x)
            return y < p.y;
        return x < p.x;
    }
};

const int maxn = 2e5 + 10;

int n, m, a[maxn], lc[maxn], rc[maxn];
point s[maxn];
vector < int > star[maxn];
vector < ll > dp[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    cin >> m;
     sort(s + 1, s + m + 1);
    for (int i = 1; i <= m; i ++)
    {
        cin >> s[i].x >> s[i].y >> s[i].c;
        star[s[i].x].push_back(i);
    }

}

int cartesian_tree()
{
    for (int i = 1; i <= n; i ++)
    {
        lc[i] = rc[i] = -1;
    }

    stack < int > st;
    for (int i = 1; i <= n; i ++)
    {
        while(!st.empty() && a[st.top()] < a[i])
        {
            lc[i] = st.top();
            st.pop();
        }

        st.push(i);
    }

    while(!st.empty())
        st.pop();
    for (int i = n; i > 0; i --)
    {
        while(!st.empty() && a[st.top()] <= a[i])
        {
            rc[i] = st.top();
            st.pop();
        }

        st.push(i);
    }

    int root;
    while(!st.empty())
    {
        root = st.top();
        st.pop();
    }
    /**cout << "cartesian tree" << endl;
    cout << root << endl;
    for (int i = 1; i <= n; i ++)
    {
        cout << lc[i] << " " << rc[i] << endl;
    }*/
    return root;
}

const ll inf = 1e18;

int rev[maxn];
ll temp[maxn];
pair < vector < ll >, vector < int > > combine(vector < ll > dp_lf, vector < ll > dp_rf,
        vector < int > ls, vector < int > rs, int height)
{

    vector < int > comb = ls;
    for (int cur : rs)
        comb.push_back(cur);
    sort(comb.begin(), comb.end());

    int lf_sz = ls.size(), rf_sz = rs.size();
    for (int i = 0; i <= lf_sz + rf_sz; i ++)
    {
        if (i > 0)
            rev[comb[i - 1]] = i;
        temp[i] = inf;
    }

    for (int i = 1; i <= lf_sz; i ++)
        for (int j = 1; j <= rf_sz; j ++)
        {
            if (s[ls[i - 1]].y > height && s[rs[j - 1]].y > height)
                continue;
            ///cout << "combine " << i << " " << j << " " << s[ls[i - 1]].y << " " << s[rs[j - 1]].y << endl;
            int idx = max(ls[i - 1], rs[j - 1]);
            temp[rev[idx]] = min(temp[rev[idx]], dp_lf[i] + dp_rf[j]);
        }

    for (int i = 1; i <= lf_sz; i ++)
    {
        temp[rev[ls[i - 1]]] = min(temp[rev[ls[i - 1]]], dp_lf[i] + dp_rf[0]);
    }

    for (int i = 1; i <= rf_sz; i ++)
    {
        temp[rev[rs[i - 1]]] = min(temp[rev[rs[i - 1]]], dp_rf[i] + dp_lf[0]);
    }

    temp[0] = min(temp[0], dp_lf[0] + dp_rf[0]);

    vector < ll > dp(comb.size() + 1);
    for (int i = 0; i <= comb.size(); i ++)
    {
        dp[i] = temp[i];
    }

    return {dp, comb};


}
void divide(int col)
{
    if (lc[col] != -1) divide(lc[col]);
    if (rc[col] != -1) divide(rc[col]);

    int col_sz = star[col].size();
    dp[col].resize(col_sz + 1);
    ll sum = 0;
    for (int i = 0; i < col_sz; i ++)
        sum += s[star[col][i]].c;

    dp[col][0] = sum;
    for (int i = 1; i <= col_sz; i ++)
        dp[col][i] = sum - s[star[col][i - 1]].c;


    if (lc[col] != -1)
    {
        pair < vector < ll >, vector < int > > cur =
            combine(dp[lc[col]], dp[col], star[lc[col]], star[col], a[col]);

        star[col] = cur.second;
        dp[col] = cur.first;
    }

    if (rc[col] != -1)
    {
        pair < vector < ll >, vector < int > > cur =
            combine(dp[rc[col]], dp[col], star[rc[col]], star[col], a[col]);

        star[col] = cur.second;
        dp[col] = cur.first;
    }
    /**cout << "step "<< col << endl;
    for (int cur : star[col])
        cout << cur << " ";
    cout << endl;
    for (int cur : dp[col])
        cout << cur << " ";
    cout << endl;*/
}
void solve()
{
    input();
    int root = cartesian_tree();
    divide(root);
    ll ans = inf;
    for (int i = 0; i <= m; i ++)
        ans = min(ans, dp[root][i]);
    cout << ans << endl;
}
int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'std::pair<std::vector<long long int>, std::vector<int> > combine(std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, int)':
constellation3.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i = 0; i <= comb.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
constellation3.cpp: In function 'int cartesian_tree()':
constellation3.cpp:91:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |     return root;
      |            ^~~~

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