oj.uz

Submission #453734

# Submission time Handle Problem Language Result Execution time Memory
453734 2021-08-04T16:25:33 Z blue Constellation 3 (JOI20_constellation3) C++17
35 / 100
 428 ms 382788 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

const int maxN = 200'000;
const int maxM = 200'000;
const int lgM = 18;
const int lgN = 18;
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;


// struct segtree
// {
//     int l;
//     int r;
//     int mx;
//
//     segtree* left = NULL;
//     segtree* right = NULL;
//
//     segtree()
//     {
//         ;
//     }
//
//     segtree(int L, int R)
//     {
//         l = L;
//         r = R;
//         if(l == r)
//         {
//             mx = A[l];
//         }
//         else
//         {
//             int m = (l+r)/2;
//             left = new segtree(l, m);
//             right = new segtree(m+1, r);
//             mx = max(left->mx, right->mx);
//         }
//     }
//
//     int rangemax(int L, int R)
//     {
//         if(R < l || r < L) return -INF;
//         else if(L <= l && r <= R) return mx;
//         else return max(left->rangemax(L, R), right->rangemax(L, R));
//     }
// };
int lowest_pow[1+maxN+1];

struct sparse_table
{
    int** mx;

    sparse_table(int N)
    {
        // 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]);
            }
        }
    }

    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];
// long long anc_dp_sum[1+maxM][lgM]; //exclusive

int** anc;
vector<int>** desc;
long long** anc_dp_sum;

vector<int> depth(1+maxM, 0);
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))
        {
            // if(dbg_flag)
            // {
            //     cerr << "jumping from " << u << " to " << anc[u][e] << ", adding " << anc_dp_sum[u][e] << " to answer\n";
            // }
            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)
{
    // cerr << "binary lift " << u << ' ' << e << '\n';
    anc_dp_sum[u][e] = anc_dp_sum[u][e-1] + anc_dp_sum[ anc[u][e-1] ][e-1];
    // cerr << "anc dp sum " << u << ' ' << e << " = " << anc_dp_sum[u][e] << '\n';

    for(int v: desc[u][e])
        binary_lift(v, e+1);
}

void dfs2(int u)
{
    // cerr << "\n\n\n\n";
    // cerr << "entered dfs2 " << u << "\n";
    for(int v: desc[u][0])
    {
        // cerr << u << " -> " << v << '\n';
        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];
        // cerr << "!!! ";
        // cerr << "dp[" << u << "] = " << dp[u] << '\n';
    }
    else
    {
        // cerr << "case 2\n";
        int sb = star_bottom[u];
        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) ];




        // cerr << sb << ' ' << child_dp_sum[sb] << ' ' << chain_sum(sb, depth[sb] - depth[u]) << ' ' << C[u] << '\n';
        // cerr << child_dp_sum[u] << '\n';
        // cerr << new_dp << '\n';

        dp[u] = max(child_dp_sum[u],   new_dp);

// cerr << "!!! ";
        // cerr << "dp[" << u << "] = " << dp[u] << '\n';
    }
    // cerr << "exited dfs2 " << u << "\n";
    // cerr << "\n\n\n\n";
}







int main()
{
    anc = new int*[1+maxM];
    desc = new vector<int>*[1+maxM];
    anc_dp_sum = new long long*[1+maxM];
    for(int i = 0; i <= 1+maxM; i++)
    {
        anc[i] = new int[lgM];
        desc[i] = new vector<int>[lgM];
        anc_dp_sum[i] = new long long[lgM];
    }


    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 <= N+1; i++)
        lowest_pow[i] = 1 + lowest_pow[i/2];





    // cerr << "total cost = " << total_cost << '\n';

    sparse_table S(N);
    // segtree S1(0, N+1);

    // cerr << "check\n";
    // cerr << "\n\n\n";


    assert(N + M <= 10000);

    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;

        // cerr << j << ' ' << left_high[j] << ' ' << right_high[j] << '\n';

        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 << "\n\n\n\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++)
    {
        // cerr << "i = " << i << '\n';
        for(int o: openings[i])
        {
            // cerr << "   o = " << o << '\n';
            // cerr << "parent " << o << " = " << ST.back() << '\n';
            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();
            // cerr << "star bottom of " << j << " = " << star_bottom[j] << '\n';
        }

        for(int c: closings[i])
        {
            ST.pop_back();
            // cerr << "   c = " << c << '\n';
        }
    }

    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++)
    {
        // cerr << "anc " << j << " = " << anc[j][0] << '\n';
        if(anc[j][0] == 0)
        {
            // cerr << "calling " << j << '\n';
            dfs2(j);
            max_kept += dp[j];
        }
    }

    cout << total_cost - max_kept << '\n';
}

Compilation message

constellation3.cpp: In function 'long long int chain_sum(int, int)':
constellation3.cpp:174:9: warning: unused variable 'u1' [-Wunused-variable]
  174 |     int u1 = u;
      |         ^~
constellation3.cpp: In function 'int main()':
constellation3.cpp:391:17: warning: unused variable 'c' [-Wunused-variable]
  391 |         for(int c: closings[i])
      |                 ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 167108 KB Output is correct
2 Correct 86 ms 167080 KB Output is correct
3 Correct 87 ms 167168 KB Output is correct
4 Correct 89 ms 167120 KB Output is correct
5 Correct 87 ms 167044 KB Output is correct
6 Correct 86 ms 167096 KB Output is correct
7 Correct 88 ms 167108 KB Output is correct
8 Correct 94 ms 167056 KB Output is correct
9 Correct 89 ms 167164 KB Output is correct
10 Correct 89 ms 167300 KB Output is correct
11 Correct 87 ms 167208 KB Output is correct
12 Correct 89 ms 167152 KB Output is correct
13 Correct 88 ms 167108 KB Output is correct
14 Correct 90 ms 167112 KB Output is correct
15 Correct 90 ms 167192 KB Output is correct
16 Correct 87 ms 167136 KB Output is correct
17 Correct 88 ms 167164 KB Output is correct
18 Correct 89 ms 167220 KB Output is correct
19 Correct 88 ms 167232 KB Output is correct
20 Correct 89 ms 167164 KB Output is correct
21 Correct 90 ms 167308 KB Output is correct
22 Correct 88 ms 167108 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 167108 KB Output is correct
2 Correct 86 ms 167080 KB Output is correct
3 Correct 87 ms 167168 KB Output is correct
4 Correct 89 ms 167120 KB Output is correct
5 Correct 87 ms 167044 KB Output is correct
6 Correct 86 ms 167096 KB Output is correct
7 Correct 88 ms 167108 KB Output is correct
8 Correct 94 ms 167056 KB Output is correct
9 Correct 89 ms 167164 KB Output is correct
10 Correct 89 ms 167300 KB Output is correct
11 Correct 87 ms 167208 KB Output is correct
12 Correct 89 ms 167152 KB Output is correct
13 Correct 88 ms 167108 KB Output is correct
14 Correct 90 ms 167112 KB Output is correct
15 Correct 90 ms 167192 KB Output is correct
16 Correct 87 ms 167136 KB Output is correct
17 Correct 88 ms 167164 KB Output is correct
18 Correct 89 ms 167220 KB Output is correct
19 Correct 88 ms 167232 KB Output is correct
20 Correct 89 ms 167164 KB Output is correct
21 Correct 90 ms 167308 KB Output is correct
22 Correct 88 ms 167108 KB Output is correct
23 Correct 93 ms 167568 KB Output is correct
24 Correct 93 ms 167544 KB Output is correct
25 Correct 92 ms 167592 KB Output is correct
26 Correct 93 ms 167568 KB Output is correct
27 Correct 92 ms 167524 KB Output is correct
28 Correct 91 ms 167616 KB Output is correct
29 Correct 92 ms 167540 KB Output is correct
30 Correct 93 ms 167584 KB Output is correct
31 Correct 93 ms 167612 KB Output is correct
32 Correct 92 ms 168040 KB Output is correct
33 Correct 92 ms 168136 KB Output is correct
34 Correct 93 ms 168056 KB Output is correct
35 Correct 95 ms 168156 KB Output is correct
36 Correct 93 ms 168192 KB Output is correct
37 Correct 92 ms 168132 KB Output is correct
38 Correct 92 ms 168132 KB Output is correct
39 Correct 91 ms 167832 KB Output is correct
40 Correct 98 ms 168132 KB Output is correct
41 Correct 93 ms 167832 KB Output is correct
42 Correct 92 ms 167756 KB Output is correct
43 Correct 94 ms 168132 KB Output is correct
44 Correct 92 ms 167748 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 167108 KB Output is correct
2 Correct 86 ms 167080 KB Output is correct
3 Correct 87 ms 167168 KB Output is correct
4 Correct 89 ms 167120 KB Output is correct
5 Correct 87 ms 167044 KB Output is correct
6 Correct 86 ms 167096 KB Output is correct
7 Correct 88 ms 167108 KB Output is correct
8 Correct 94 ms 167056 KB Output is correct
9 Correct 89 ms 167164 KB Output is correct
10 Correct 89 ms 167300 KB Output is correct
11 Correct 87 ms 167208 KB Output is correct
12 Correct 89 ms 167152 KB Output is correct
13 Correct 88 ms 167108 KB Output is correct
14 Correct 90 ms 167112 KB Output is correct
15 Correct 90 ms 167192 KB Output is correct
16 Correct 87 ms 167136 KB Output is correct
17 Correct 88 ms 167164 KB Output is correct
18 Correct 89 ms 167220 KB Output is correct
19 Correct 88 ms 167232 KB Output is correct
20 Correct 89 ms 167164 KB Output is correct
21 Correct 90 ms 167308 KB Output is correct
22 Correct 88 ms 167108 KB Output is correct
23 Correct 93 ms 167568 KB Output is correct
24 Correct 93 ms 167544 KB Output is correct
25 Correct 92 ms 167592 KB Output is correct
26 Correct 93 ms 167568 KB Output is correct
27 Correct 92 ms 167524 KB Output is correct
28 Correct 91 ms 167616 KB Output is correct
29 Correct 92 ms 167540 KB Output is correct
30 Correct 93 ms 167584 KB Output is correct
31 Correct 93 ms 167612 KB Output is correct
32 Correct 92 ms 168040 KB Output is correct
33 Correct 92 ms 168136 KB Output is correct
34 Correct 93 ms 168056 KB Output is correct
35 Correct 95 ms 168156 KB Output is correct
36 Correct 93 ms 168192 KB Output is correct
37 Correct 92 ms 168132 KB Output is correct
38 Correct 92 ms 168132 KB Output is correct
39 Correct 91 ms 167832 KB Output is correct
40 Correct 98 ms 168132 KB Output is correct
41 Correct 93 ms 167832 KB Output is correct
42 Correct 92 ms 167756 KB Output is correct
43 Correct 94 ms 168132 KB Output is correct
44 Correct 92 ms 167748 KB Output is correct
45 Runtime error 428 ms 382788 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -