제출 #851765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851765		danikoynov	별자리 3 (JOI20_constellation3)	C++14	35 / 100	891 ms	524288 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 poll
{
    ll x, y, c;
    bool operator < (const poll &p) const
    {
        if (y == p.y)
            return x < p.x;
        return y < p.y;
    }
};

const ll maxn = 2e5 + 10;

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

    cin >> m;


    for (ll i = 1; i <= m; i ++)
    {
        cin >> s[i].x >> s[i].y >> s[i].c;
    }

    sort(s + 1, s + m + 1);

    for (ll i = 1; i <= m; i ++)
    {

        star[s[i].x].push_back(i);
    }
}

ll cartesian_tree()
{

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

    stack < ll > st;
    for (ll 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 (ll i = n; i > 0; i --)
    {
        while(!st.empty() && a[st.top()] <= a[i])
        {
            rc[i] = st.top();
            st.pop();
        }

        st.push(i);
    }

    ll root;
    while(!st.empty())
    {

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

const ll inf = 1e18;

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

    int p1 = 0;
    int p2 = 0;
    vector < ll > comb;
    while(p1 < ls.size() && p2 < rs.size())
    {
        if (ls[p1] < rs[p2])
            comb.push_back(ls[p1 ++]);
        else
            comb.push_back(rs[p2 ++]);
    }
    while(p1 < ls.size())
        comb.push_back(ls[p1 ++]);
    while(p2 < rs.size())
        comb.push_back(rs[p2 ++]);


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



    /**for (ll i = 1; i <= lf_sz; i ++)
        for (ll 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;
            ll idx = max(ls[i - 1], rs[j - 1]);
            temp[rev[idx]] = min(temp[rev[idx]], dp_lf[i] + dp_rf[j]);
        }*/

    int pt = 1;
    ll best = dp_rf[0];
    for (ll i = 1; i <= lf_sz; i ++)
    {
        while(pt <= rf_sz && s[rs[pt - 1]].y <= min(s[ls[i - 1]].y, height))
        {
            best = min(best, dp_rf[pt]);
            pt ++;
        }
        temp[rev[ls[i - 1]]] = min(temp[rev[ls[i - 1]]], dp_lf[i] + best);
    }

    pt = 1;
    best = dp_lf[0];
    for (ll i = 1; i <= rf_sz; i ++)
    {
        while(pt <= lf_sz && s[ls[pt - 1]].y <= min(s[rs[i - 1]].y, height))
        {
            best = min(best, dp_lf[pt]);
            pt ++;
        }
        temp[rev[rs[i - 1]]] = min(temp[rev[rs[i - 1]]], dp_rf[i] + best);
    }

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

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

    vector < ll > new_dp, new_comb;
    ll und = dp[0];
    for (int i = 1; i <= comb.size(); i ++)
        if (s[comb[i - 1]].y <= height)
            und = min(und, dp[i]);

    new_dp.push_back(und);
    for (int i = 1; i <= comb.size(); i ++)
    {
        if (s[comb[i - 1]].y > height && new_dp.back() > dp[i])
        {
            new_dp.push_back(dp[i]);
            new_comb.push_back(comb[i - 1]);
        }
    }


    return {new_dp, new_comb};


}
void divide(ll col)
{

    if (lc[col] != -1) divide(lc[col]);
    if (rc[col] != -1) divide(rc[col]);

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

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


    if (lc[col] != -1)
    {
        pair < vector < ll >, vector < ll > > 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 < ll > > 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 (ll cur : star[col])
        cout << cur << " ";
    cout << endl;
    for (ll cur : dp[col])
        cout << cur << " ";
    cout << endl;*/
}
void solve()
{
    input();
    ll root = cartesian_tree();

    divide(root);
    ll ans = inf;
    for (ll i = 0; i < dp[root].size(); i ++)
        ans = min(ans, dp[root][i]);
    cout << ans << endl;
}
int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

/**
5
3 2 2 2 3
3
1 5 3
4 3 2
2 4 2

*/

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > combine(std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&, ll)':
constellation3.cpp:114:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     while(p1 < ls.size() && p2 < rs.size())
      |           ~~~^~~~~~~~~~~
constellation3.cpp:114:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     while(p1 < ls.size() && p2 < rs.size())
      |                             ~~~^~~~~~~~~~~
constellation3.cpp:121:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     while(p1 < ls.size())
      |           ~~~^~~~~~~~~~~
constellation3.cpp:123:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     while(p2 < rs.size())
      |           ~~~^~~~~~~~~~~
constellation3.cpp:174:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (ll i = 0; i <= comb.size(); i ++)
      |                    ~~^~~~~~~~~~~~~~
constellation3.cpp:181:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for (int i = 1; i <= comb.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
constellation3.cpp:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (int i = 1; i <= comb.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
constellation3.cpp: In function 'void solve()':
constellation3.cpp:251:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |     for (ll i = 0; i < dp[root].size(); i ++)
      |                    ~~^~~~~~~~~~~~~~~~~
constellation3.cpp: In function 'll cartesian_tree()':
constellation3.cpp:100:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     return root;
      |            ^~~~

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