oj.uz

Submission #453705

# Submission time Handle Problem Language Result Execution time Memory
453705 2021-08-04T15:47:31 Z blue Constellation 3 (JOI20_constellation3) C++17
35 / 100
 1500 ms 142924 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

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


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))
        {
            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];
                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;



        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()
{
    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];
    }
    cerr << "total cost = " << total_cost << '\n';

    segtree S(0, N+1);

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


    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:131:9: warning: unused variable 'u1' [-Wunused-variable]
  131 |     int u1 = u;
      |         ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 112716 KB Output is correct
2 Correct 109 ms 112468 KB Output is correct
3 Correct 108 ms 112444 KB Output is correct
4 Correct 109 ms 112452 KB Output is correct
5 Correct 112 ms 112488 KB Output is correct
6 Correct 107 ms 112568 KB Output is correct
7 Correct 103 ms 112396 KB Output is correct
8 Correct 111 ms 112436 KB Output is correct
9 Correct 106 ms 112424 KB Output is correct
10 Correct 134 ms 112708 KB Output is correct
11 Correct 125 ms 112632 KB Output is correct
12 Correct 129 ms 112604 KB Output is correct
13 Correct 151 ms 112580 KB Output is correct
14 Correct 134 ms 112596 KB Output is correct
15 Correct 126 ms 112536 KB Output is correct
16 Correct 142 ms 112624 KB Output is correct
17 Correct 128 ms 112520 KB Output is correct
18 Correct 124 ms 112616 KB Output is correct
19 Correct 123 ms 112532 KB Output is correct
20 Correct 115 ms 112540 KB Output is correct
21 Correct 131 ms 112668 KB Output is correct
22 Correct 126 ms 112588 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 112716 KB Output is correct
2 Correct 109 ms 112468 KB Output is correct
3 Correct 108 ms 112444 KB Output is correct
4 Correct 109 ms 112452 KB Output is correct
5 Correct 112 ms 112488 KB Output is correct
6 Correct 107 ms 112568 KB Output is correct
7 Correct 103 ms 112396 KB Output is correct
8 Correct 111 ms 112436 KB Output is correct
9 Correct 106 ms 112424 KB Output is correct
10 Correct 134 ms 112708 KB Output is correct
11 Correct 125 ms 112632 KB Output is correct
12 Correct 129 ms 112604 KB Output is correct
13 Correct 151 ms 112580 KB Output is correct
14 Correct 134 ms 112596 KB Output is correct
15 Correct 126 ms 112536 KB Output is correct
16 Correct 142 ms 112624 KB Output is correct
17 Correct 128 ms 112520 KB Output is correct
18 Correct 124 ms 112616 KB Output is correct
19 Correct 123 ms 112532 KB Output is correct
20 Correct 115 ms 112540 KB Output is correct
21 Correct 131 ms 112668 KB Output is correct
22 Correct 126 ms 112588 KB Output is correct
23 Correct 440 ms 114156 KB Output is correct
24 Correct 497 ms 114272 KB Output is correct
25 Correct 438 ms 114160 KB Output is correct
26 Correct 459 ms 114244 KB Output is correct
27 Correct 467 ms 114260 KB Output is correct
28 Correct 443 ms 114264 KB Output is correct
29 Correct 432 ms 114328 KB Output is correct
30 Correct 452 ms 114228 KB Output is correct
31 Correct 425 ms 114288 KB Output is correct
32 Correct 686 ms 115364 KB Output is correct
33 Correct 686 ms 115520 KB Output is correct
34 Correct 680 ms 115396 KB Output is correct
35 Correct 675 ms 115540 KB Output is correct
36 Correct 698 ms 115420 KB Output is correct
37 Correct 692 ms 115476 KB Output is correct
38 Correct 597 ms 115212 KB Output is correct
39 Correct 603 ms 114912 KB Output is correct
40 Correct 661 ms 115352 KB Output is correct
41 Correct 610 ms 115000 KB Output is correct
42 Correct 609 ms 114800 KB Output is correct
43 Correct 675 ms 115464 KB Output is correct
44 Correct 592 ms 114812 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 112716 KB Output is correct
2 Correct 109 ms 112468 KB Output is correct
3 Correct 108 ms 112444 KB Output is correct
4 Correct 109 ms 112452 KB Output is correct
5 Correct 112 ms 112488 KB Output is correct
6 Correct 107 ms 112568 KB Output is correct
7 Correct 103 ms 112396 KB Output is correct
8 Correct 111 ms 112436 KB Output is correct
9 Correct 106 ms 112424 KB Output is correct
10 Correct 134 ms 112708 KB Output is correct
11 Correct 125 ms 112632 KB Output is correct
12 Correct 129 ms 112604 KB Output is correct
13 Correct 151 ms 112580 KB Output is correct
14 Correct 134 ms 112596 KB Output is correct
15 Correct 126 ms 112536 KB Output is correct
16 Correct 142 ms 112624 KB Output is correct
17 Correct 128 ms 112520 KB Output is correct
18 Correct 124 ms 112616 KB Output is correct
19 Correct 123 ms 112532 KB Output is correct
20 Correct 115 ms 112540 KB Output is correct
21 Correct 131 ms 112668 KB Output is correct
22 Correct 126 ms 112588 KB Output is correct
23 Correct 440 ms 114156 KB Output is correct
24 Correct 497 ms 114272 KB Output is correct
25 Correct 438 ms 114160 KB Output is correct
26 Correct 459 ms 114244 KB Output is correct
27 Correct 467 ms 114260 KB Output is correct
28 Correct 443 ms 114264 KB Output is correct
29 Correct 432 ms 114328 KB Output is correct
30 Correct 452 ms 114228 KB Output is correct
31 Correct 425 ms 114288 KB Output is correct
32 Correct 686 ms 115364 KB Output is correct
33 Correct 686 ms 115520 KB Output is correct
34 Correct 680 ms 115396 KB Output is correct
35 Correct 675 ms 115540 KB Output is correct
36 Correct 698 ms 115420 KB Output is correct
37 Correct 692 ms 115476 KB Output is correct
38 Correct 597 ms 115212 KB Output is correct
39 Correct 603 ms 114912 KB Output is correct
40 Correct 661 ms 115352 KB Output is correct
41 Correct 610 ms 115000 KB Output is correct
42 Correct 609 ms 114800 KB Output is correct
43 Correct 675 ms 115464 KB Output is correct
44 Correct 592 ms 114812 KB Output is correct
45 Execution timed out 1589 ms 142924 KB Time limit exceeded
46 Halted 0 ms 0 KB -