Submission #493975

#	Time	Username	Problem	Language	Result	Execution time	Memory
493975		blue	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	1592 ms	246484 KiB

constellation3

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
const int maxN = 200'000;
const int maxM = 200'000;
const int lgM = 17;
const int lgN = 17;
const int INF = 1'000'000'000;
 
int N;
vector<int> A(1+maxN+1);
vector<int> star_list[1+maxN];
 
int M;
vector<int> X(1+maxM);
vector<int> Y(1+maxM);
vector<long long> C(1+maxM);
 
long long total_cost = 0;
 
vector<int> lowest_pow(100+maxN);
 
struct sparse_table
{
    int** mx;
 
    sparse_table()
    {
        // cerr << "creating sparse table\n";
        mx = new int*[1+N+1];
        for(int i = 0; i <= N+1; i++)
            mx[i] = new int[lgN];
 
        for(int i = 0; i <= N+1; i++)
            mx[i][0] = A[i];
 
        for(int e = 1; e < lgN; e++)
        {
            for(int i = 0; i <= N+1; i++)
            {
                if(i + (1 << e) - 1 > N+1)
                    continue;
 
                mx[i][e] = max(mx[i][e-1], mx[i + (1 << (e-1))][e-1]);
            }
        }
        // cerr << "sparse table built\n";
    }
 
    int rangemax(int l, int r)
    {
        // cerr << "range max " << l << ' ' << r << '\n';
        int p = lowest_pow[r-l+1];
        // cerr << "p = " << p << '\n';
        return max(mx[l][p], mx[r - (1 << p) + 1][p]);
    }
};
 
 
 
vector<int> left_high(1+maxM);
vector<int> right_high(1+maxM);
 
 
struct rectangle
{
    int L; //[L, R] x [H, N]
    int R;
    int H;
    int I;
};
 
bool operator < (rectangle A, rectangle B)
{
    if(A.L != B.L)
        return A.L < B.L;
    else if(A.R != B.R)
        return A.R > B.R;
    else if(A.H != B.H)
        return A.H > B.H;
    else
        return A.I < B.I;
}
 
vector<rectangle> rect(1+maxM);
vector<int> star_bottom(1+maxM);
 
vector<int> openings[1+maxN];
vector<int> closings[1+maxN];
 
 
 
int anc[1+maxM][lgM];
vector<int> desc[1+maxM][lgM];
vector<int> depth(1+maxM, 0);
 
long long anc_dp_sum[1+maxM][lgM]; //exclusive
vector<long long> dp(1+maxM, 0LL);
vector<long long> child_dp_sum(1+maxM, 0LL);
 
 
bool dbg_flag = 0;
 
 
 
 
void dfs1(int u)
{
    for(int v: desc[u][0])
    {
        depth[v] = depth[u] + 1;
        dfs1(v);
    }
}
 
int getAnc(int u, int d)
{
    for(int e = 0; e < lgM; e++)
    {
        if(d & (1 << e))
            u = anc[u][e];
    }
    return u;
}
 
long long chain_sum(int u, int d)
{
    int u1 = u;
    long long ans = 0;
    for(int e = 0; e < lgM; e++)
    {
        if(d & (1 << e))
        {
            ans += anc_dp_sum[u][e];
            u = anc[u][e];
        }
    }
    // cerr << "chain sum " << u1 << ' ' << d << " " << ans << '\n';
    return ans;
}
 
 
 
 
void binary_lift(int u, int e)
{
    anc_dp_sum[u][e] = anc_dp_sum[u][e-1] + anc_dp_sum[ anc[u][e-1] ][e-1];
 
    for(int v: desc[u][e])
        binary_lift(v, e+1);
}
 
void dfs2(int u)
{
    for(int v: desc[u][0])
    {
        dfs2(v);
        child_dp_sum[u] += dp[v];
    }
 
    for(int v: desc[u][0])
    {
        anc_dp_sum[v][0] = child_dp_sum[u] - dp[v];
        // cerr << "anc dp sum " << v << ' ' << 0 << " = " << anc_dp_sum[v][0] << '\n';
        for(int v2: desc[v][0])
            binary_lift(v2, 1);
    }
    if(star_bottom[u] == u)
    {
        dp[u] = child_dp_sum[u] + C[u];
    }
    else
    {
        int sb = star_bottom[u];
                dbg_flag = 1;
        long long new_dp = child_dp_sum[sb] + chain_sum(sb, depth[sb] - depth[u]) + C[u];
        // new_dp += child_dp_sum[u] - dp[ getAnc(sb, depth[sb] - depth[u] - 1) ];
 
        dbg_flag = 0;
 
 
        dp[u] = max(child_dp_sum[u],   new_dp);
 
    }
}
 
 
 
int main()
{
  	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
    cin >> N;
    A[0] = N+1;
    for(int i = 1; i <= N; i++) cin >> A[i];
    A[N+1] = N+1;
 
    cin >> M;
    for(int j = 1; j <= M; j++)
    {
        cin >> X[j] >> Y[j] >> C[j];
        star_list[ X[j] ].push_back(j);
        total_cost += C[j];
    }
 
    lowest_pow[1] = 0;
    for(int i = 2; i < lowest_pow.size(); i++)
        lowest_pow[i] = 1 + lowest_pow[i/2];
 
    sparse_table S;
 
    for(int j = 1; j <= M; j++)
    {
        // cerr << "j = " << j << '\n';
        int lo, hi, mid;
        //closest building on left
        lo = 0;
        hi = X[j]-1;
        while(lo != hi)
        {
            mid = (lo+hi)/2+1;
            if(S.rangemax(mid, hi) >= Y[j])
                lo = mid;
            else
                hi = mid-1;
        }
        left_high[j] = lo;
 
        // cerr << "part 1 done\n";
 
 
        //closest building on right
        lo = X[j]+1;
        hi = N+1;
        while(lo != hi)
        {
            // cerr << lo << ' ' << hi << '\n';
            mid = (lo+hi)/2;
            if(S.rangemax(lo, mid) >= Y[j])
                hi = mid;
            else
                lo = mid+1;
        }
        right_high[j] = lo;
 
 
        rect[j] = rectangle{left_high[j] + 1, right_high[j] - 1, Y[j], j};
        openings[rect[j].L].push_back(j);
        closings[rect[j].R].push_back(j);
        // cerr << "done\n";
    }
    // cerr << "check\n";
 
 
    for(int i = 1; i <= N; i++)
    {
        // cerr << "i = " << i << '\n';
        sort(openings[i].begin(), openings[i].end(), [] (int o1, int o2)
        {
            return rect[o1] < rect[o2];
        });
 
        // for(int o: openings[i]) cerr << o << ' ';
        // cerr << '\n';
 
        sort(closings[i].begin(), closings[i].end(), [] (int c1, int c2)
        {
            return rect[c2] < rect[c1]; //  REVERSED!!!!!!
        });
 
        // for(int c: closings[i]) cerr << c << ' ';
        // cerr << '\n';
    }
 
    vector<int> ST(1, 0);
    anc[0][0] = 0;
    for(int i = 1; i <= N; i++)
    {
        for(int o: openings[i])
        {
            anc[o][0] = ST.back();
            desc[ anc[o][0] ][0].push_back(o);
            ST.push_back(o);
        }
 
        for(int j: star_list[i])
        {
            star_bottom[j] = ST.back();
        }
 
        for(int c: closings[i])
        {
            ST.pop_back();
        }
    }
 
    for(int e = 1; e < lgM; e++)
        for(int j = 0; j <= M; j++)
        {
            anc[j][e] = anc[ anc[j][e-1] ][e-1];
            desc[ anc[j][e] ][e].push_back(j);
        }
 
    for(int j = 1; j <= M; j++)
        if(anc[j][0] == 0)
        {
            depth[j] = 1;
            dfs1(j);
        }
 
    long long max_kept = 0;
 
 
    for(int j = 1; j <= M; j++)
    {
        if(anc[j][0] == 0)
        {
            dfs2(j);
            max_kept += dp[j];
        }
    }
 
    cout << total_cost - max_kept << '\n';
}

Compilation message (stderr)

constellation3.cpp: In function 'long long int chain_sum(int, int)':
constellation3.cpp:131:9: warning: unused variable 'u1' [-Wunused-variable]
  131 |     int u1 = u;
      |         ^~
constellation3.cpp: In function 'int main()':
constellation3.cpp:211:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |     for(int i = 2; i < lowest_pow.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:295:17: warning: unused variable 'c' [-Wunused-variable]
  295 |         for(int c: closings[i])
      |                 ^

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