oj.uz

답안 #453736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
453736 2021-08-04T16:25:55 Z blue 별자리 3 (JOI20_constellation3) C++17
35 / 100
 1500 ms 221728 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

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 167108 KB Output is correct
2 Correct 91 ms 167168 KB Output is correct
3 Correct 98 ms 167168 KB Output is correct
4 Correct 95 ms 167116 KB Output is correct
5 Correct 91 ms 167108 KB Output is correct
6 Correct 96 ms 167124 KB Output is correct
7 Correct 95 ms 167200 KB Output is correct
8 Correct 95 ms 167176 KB Output is correct
9 Correct 96 ms 167168 KB Output is correct
10 Correct 87 ms 167184 KB Output is correct
11 Correct 92 ms 167132 KB Output is correct
12 Correct 88 ms 167108 KB Output is correct
13 Correct 100 ms 167156 KB Output is correct
14 Correct 91 ms 167108 KB Output is correct
15 Correct 89 ms 167140 KB Output is correct
16 Correct 96 ms 167176 KB Output is correct
17 Correct 91 ms 167080 KB Output is correct
18 Correct 97 ms 167112 KB Output is correct
19 Correct 88 ms 167092 KB Output is correct
20 Correct 92 ms 167108 KB Output is correct
21 Correct 92 ms 167256 KB Output is correct
22 Correct 91 ms 167176 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 167108 KB Output is correct
2 Correct 91 ms 167168 KB Output is correct
3 Correct 98 ms 167168 KB Output is correct
4 Correct 95 ms 167116 KB Output is correct
5 Correct 91 ms 167108 KB Output is correct
6 Correct 96 ms 167124 KB Output is correct
7 Correct 95 ms 167200 KB Output is correct
8 Correct 95 ms 167176 KB Output is correct
9 Correct 96 ms 167168 KB Output is correct
10 Correct 87 ms 167184 KB Output is correct
11 Correct 92 ms 167132 KB Output is correct
12 Correct 88 ms 167108 KB Output is correct
13 Correct 100 ms 167156 KB Output is correct
14 Correct 91 ms 167108 KB Output is correct
15 Correct 89 ms 167140 KB Output is correct
16 Correct 96 ms 167176 KB Output is correct
17 Correct 91 ms 167080 KB Output is correct
18 Correct 97 ms 167112 KB Output is correct
19 Correct 88 ms 167092 KB Output is correct
20 Correct 92 ms 167108 KB Output is correct
21 Correct 92 ms 167256 KB Output is correct
22 Correct 91 ms 167176 KB Output is correct
23 Correct 91 ms 167520 KB Output is correct
24 Correct 94 ms 167544 KB Output is correct
25 Correct 94 ms 167620 KB Output is correct
26 Correct 93 ms 167620 KB Output is correct
27 Correct 91 ms 167620 KB Output is correct
28 Correct 91 ms 167592 KB Output is correct
29 Correct 95 ms 167492 KB Output is correct
30 Correct 94 ms 167620 KB Output is correct
31 Correct 92 ms 167568 KB Output is correct
32 Correct 95 ms 168132 KB Output is correct
33 Correct 94 ms 168148 KB Output is correct
34 Correct 94 ms 168132 KB Output is correct
35 Correct 93 ms 168132 KB Output is correct
36 Correct 92 ms 168120 KB Output is correct
37 Correct 93 ms 168092 KB Output is correct
38 Correct 91 ms 168132 KB Output is correct
39 Correct 93 ms 167716 KB Output is correct
40 Correct 94 ms 168220 KB Output is correct
41 Correct 95 ms 167776 KB Output is correct
42 Correct 94 ms 167700 KB Output is correct
43 Correct 95 ms 168176 KB Output is correct
44 Correct 95 ms 167832 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 167108 KB Output is correct
2 Correct 91 ms 167168 KB Output is correct
3 Correct 98 ms 167168 KB Output is correct
4 Correct 95 ms 167116 KB Output is correct
5 Correct 91 ms 167108 KB Output is correct
6 Correct 96 ms 167124 KB Output is correct
7 Correct 95 ms 167200 KB Output is correct
8 Correct 95 ms 167176 KB Output is correct
9 Correct 96 ms 167168 KB Output is correct
10 Correct 87 ms 167184 KB Output is correct
11 Correct 92 ms 167132 KB Output is correct
12 Correct 88 ms 167108 KB Output is correct
13 Correct 100 ms 167156 KB Output is correct
14 Correct 91 ms 167108 KB Output is correct
15 Correct 89 ms 167140 KB Output is correct
16 Correct 96 ms 167176 KB Output is correct
17 Correct 91 ms 167080 KB Output is correct
18 Correct 97 ms 167112 KB Output is correct
19 Correct 88 ms 167092 KB Output is correct
20 Correct 92 ms 167108 KB Output is correct
21 Correct 92 ms 167256 KB Output is correct
22 Correct 91 ms 167176 KB Output is correct
23 Correct 91 ms 167520 KB Output is correct
24 Correct 94 ms 167544 KB Output is correct
25 Correct 94 ms 167620 KB Output is correct
26 Correct 93 ms 167620 KB Output is correct
27 Correct 91 ms 167620 KB Output is correct
28 Correct 91 ms 167592 KB Output is correct
29 Correct 95 ms 167492 KB Output is correct
30 Correct 94 ms 167620 KB Output is correct
31 Correct 92 ms 167568 KB Output is correct
32 Correct 95 ms 168132 KB Output is correct
33 Correct 94 ms 168148 KB Output is correct
34 Correct 94 ms 168132 KB Output is correct
35 Correct 93 ms 168132 KB Output is correct
36 Correct 92 ms 168120 KB Output is correct
37 Correct 93 ms 168092 KB Output is correct
38 Correct 91 ms 168132 KB Output is correct
39 Correct 93 ms 167716 KB Output is correct
40 Correct 94 ms 168220 KB Output is correct
41 Correct 95 ms 167776 KB Output is correct
42 Correct 94 ms 167700 KB Output is correct
43 Correct 95 ms 168176 KB Output is correct
44 Correct 95 ms 167832 KB Output is correct
45 Execution timed out 1600 ms 221728 KB Time limit exceeded
46 Halted 0 ms 0 KB -