Submission #217167

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217167	2020-03-29T07:13:00 Z	rama_pang	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	667 ms	45696 KB

constellation3

#include <bits/stdc++.h>
using namespace std;

class Dyanmic_Programming { // O(N^2) DP solution
 
 private:

  int N, M;
  int A[2005], X[2005], Y[2005], C[2005];

  long long DP[2005][2005]; // DP[height][column] = DP with domain(height, column) if we are forced to pick cell (heigth, column).
  int Star[2005][2005];

  void init() {
    for (int i = 0; i < M; i++) {
      for (int height = Y[i]; height <= N + 1; height++) {
        Star[height][X[i]] = max(Star[height][X[i]], C[i]);
      }
    }
  }
 
 public:

  long long solve() {
    init();

    for (int height = 1; height <= N + 1; height++) { // height N + 1 to merge all components into one
      for (int left = 1, right = left; left <= N; left = (++right)) {
        if (A[left] >= height) continue; // this cell is still occupied by a building (white cell).
        while (right + 1 <= N && A[right + 1] < height) {
          right++;
        }

        // column = left...right is connected to each other, now we find the transition
        vector<pair<pair<int, int>, long long>> maximum_values; // maximum values of disjoint domains for cells [height - 1][left...right]
        
        for (int l = left, r = l; l <= right; l = (++r)) {
          if (A[l] >= height - 1) continue;
          while (r + 1 <= right && A[r + 1] < height - 1) {
            r++;
          }

          { // with star
            long long mx = 0;
            for (int k = l; k <= r; k++) {
              mx = max(mx, DP[height - 1][k]);
            }
            maximum_values.push_back({{l, r}, mx});
          }
        }

        long long sum_max_values = 0;
        for (auto &values : maximum_values) {
          sum_max_values += values.second;
        }

        for (int column = left; column <= right; column++) {
          DP[height][column] = sum_max_values + Star[height][column];
        }

        for (auto &values : maximum_values) {
          for (int column = values.first.first; column <= values.first.second; column++) {
            DP[height][column] -= values.second; // This is not necessarily the correct domain and forbidden, so we subtract it 
            DP[height][column] += DP[height - 1][column] - Star[height - 1][column]; // This is the real domain and forbidden, minus the Star in (height - 1, column).
          }
        } 
      }
    }

    long long sum_all = 0;
    long long maximum = 0;
    
    for (int i = 0; i < M; i++) {
      sum_all += C[i];
    }

    for (int i = N + 1; i >= 1; i--) {
      for (int j = 1; j <= N; j++) {
        if (i == N + 1 ) {
          maximum = max(maximum, DP[i][j]);
        }
      }
    }

    return sum_all - maximum; 
  }

  void read() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
      cin >> A[i];
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
      cin >> X[i] >> Y[i] >> C[i];
    }
  }
};

class Constellation {

 private:

  int N, M;
  vector<int> A, X, Y, C;

  class DisjointSet {

   public:
   
    vector<int> p;

    DisjointSet(int n) {
      p.resize(n);
      iota(begin(p), end(p), 0);
    }
    
    int Find(int x) {
      return p[x] == x ? x : p[x] = Find(p[x]);
    }
  };

  class SegmentTree {

   private:

    vector<long long> tree;
    vector<long long> lazy;
    int sz;

    void push(int n) {
      for (int c = 0; c < 2; c++) {
        tree[n * 2 + c] += lazy[n];
        lazy[n * 2 + c] += lazy[n];
      }
      lazy[n] = 0;
    }

    void pull(int n) {
      tree[n] = max(tree[n * 2], tree[n * 2 + 1]);
    }

    void RangeSumUpdate(int n, int tl, int tr, int l, int r, long long x) {
      if (tr < l || r < tl || tl > tr || l > r) return;
      if (l <= tl && tr <= r) {
        tree[n] += x;
        lazy[n] += x;
        return;
      }
      push(n);
      int mid = (tl + tr) / 2;
      RangeSumUpdate(n * 2, tl, mid, l, r, x);
      RangeSumUpdate(n * 2 + 1, mid + 1, tr, l, r, x);
      pull(n);
    }

    long long RangeMaximumQuery(int n, int tl, int tr, int l, int r) {
      if (tr < l || r < tl || tl > tr || l > r) return 0;
      if (l <= tl && tr <= r) return tree[n];
      push(n);
      int mid = (tl + tr) / 2;
      return max(RangeMaximumQuery(n * 2, tl, mid, l, r), 
                  RangeMaximumQuery(n * 2 + 1, mid + 1, tr, l, r));
    }
  
   public:

    SegmentTree(int n) {
      sz = n;
      tree.assign(4 * n, 0);
      lazy.assign(4 * n, 0);
    }

    void RangeSumUpdate(int l, int r, long long x) {
      return RangeSumUpdate(1, 0, sz - 1, l, r, x);
    }

    long long RangeMaximumQuery(int l, int r) {
      return RangeMaximumQuery(1, 0, sz - 1, l, r);
    }

  };

  vector<vector<pair<int, int>>> CalculateStarDifference() {
    vector<vector<pair<int, int>>> StarDifference(N + 2); // SD[height] = Points where Star[height][column] - Star[height - 1][column] > 0, with (column, value)
    
    vector<vector<int>> YCoordinates(N + 1);
    vector<vector<int>> stars_per_column(N + 1);

    for (int i = 0; i < M; i++) {
      YCoordinates[X[i]].emplace_back(Y[i]);
    }

    for (int i = 1; i <= N; i++) {
      sort(begin(YCoordinates[i]), end(YCoordinates[i]));
      YCoordinates[i].resize(unique(begin(YCoordinates[i]), end(YCoordinates[i])) - begin(YCoordinates[i]));
    }

    for (int i = 1; i <= N; i++) {
      stars_per_column[i].resize(YCoordinates[i].size());
    }

    for (int i = 0; i < M; i++) {
      int where = lower_bound(begin(YCoordinates[X[i]]), end(YCoordinates[X[i]]), Y[i]) - begin(YCoordinates[X[i]]);
      stars_per_column[X[i]][where] = max(stars_per_column[X[i]][where], C[i]);
    }

    for (int i = 1; i <= N; i++) {
      for (int j = 1; j < stars_per_column[i].size(); j++) {
        stars_per_column[i][j] = max(stars_per_column[i][j], stars_per_column[i][j - 1]);
      }
    }

    for (int i = 1; i <= N; i++) {
      for (int j = 0; j < stars_per_column[i].size(); j++) {
        int value = stars_per_column[i][j] - (j > 0 ? stars_per_column[i][j - 1] : 0);
        StarDifference[YCoordinates[i][j]].emplace_back(i, value);
      }
    }

    return StarDifference;
  }

  vector<vector<int>> CalculateBuildingsWithHeight() {
    vector<vector<int>> BuildingsWithHeight(N + 2); // bwh[height] = A[i] such that A[i] = height - 1
    
    for (int i = 1; i <= N; i++) {
      BuildingsWithHeight[A[i] + 1].emplace_back(i);
    }
    
    return BuildingsWithHeight;
  }

  long long SumAll() { // sum of all C[i]
    long long res = 0;
    for (int i = 0; i < M; i++) {
      res += C[i];
    }
    return res;
  }

 public:

  void read() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N;

    A.resize(N + 1);

    for (int i = 1; i <= N; i++) {
      cin >> A[i];
    }

    cin >> M;

    X.resize(M);
    Y.resize(M);
    C.resize(M);

    for (int i = 0; i < M; i++) {
      cin >> X[i] >> Y[i] >> C[i];
    }
  }

  long long solve() {
    // initialization

    vector<vector<pair<int, int>>> StarDifference; // Points where Star[height][column] - Star[height - 1][column] > 0, with (height, value)
    StarDifference = CalculateStarDifference();

    vector<vector<int>> BuildingsWithHeight(N + 2); // BWH[height] = A[i] such that A[i] = height - 1
    BuildingsWithHeight = CalculateBuildingsWithHeight();

    // DP optimized with Segment Tree

    SegmentTree seg(N + 1);
    DisjointSet left_bound(N + 1), right_bound(N + 1); // left and right bound of components

    vector<bool> active(N + 1, false); // determine if column is already active (height > A[column])

    for (int height = 1; height <= N + 1; height++) {
      // Merge Components

      vector<pair<int, int>> LR_bounds_old; // to-be-merged components of height - 1
      vector<pair<int, int>> LR_bounds_new; // result of merged components of height
      
      for (auto &col : BuildingsWithHeight[height]) {
        if (col - 1 >= 1 && active[col - 1]) {
          int l = left_bound.Find(col - 1);
          int r = right_bound.Find(col - 1);
          assert(r == col - 1);
          LR_bounds_old.emplace_back(l, r);
        }
        if (col + 1 <= N && active[col + 1]) {
          int l = left_bound.Find(col + 1);
          int r = right_bound.Find(col + 1);
          assert(l == col + 1);
          LR_bounds_old.emplace_back(l, r);
        }
      }

      for (auto &col : BuildingsWithHeight[height]) {
        active[col] = true;
        if (col - 1 >= 1 && active[col - 1]) {
          left_bound.p[col] = col - 1;
          right_bound.p[col - 1] = col;
        }
        if (col + 1 <= N && active[col + 1]) {
          right_bound.p[col] = col + 1;
          left_bound.p[col + 1] = col;
        }
      }

      for (auto &col : BuildingsWithHeight[height]) {
        int l = col, r = col;
        if (col - 1 >= 1 && active[col - 1]) l = left_bound.Find(col - 1);
        if (col + 1 <= N && active[col + 1]) r = right_bound.Find(col + 1);  
        LR_bounds_new.emplace_back(l, r);
      }
      
      sort(begin(LR_bounds_old), end(LR_bounds_old));
      LR_bounds_old.resize(unique(begin(LR_bounds_old), end(LR_bounds_old)) - begin(LR_bounds_old));

      sort(begin(LR_bounds_new), end(LR_bounds_new));
      LR_bounds_new.resize(unique(begin(LR_bounds_new), end(LR_bounds_new)) - begin(LR_bounds_new));
      
      // Update the DP on Segment Tree

      // Add sum_of_maximums_of_previous_components - maximum_this_component
      int ptr = 0;
      for (auto &new_component : LR_bounds_new) {
        long long sum_of_maximums = 0;
        for (; ptr < LR_bounds_old.size(); ptr++) {
          if (new_component.first <= LR_bounds_old[ptr].first && LR_bounds_old[ptr].second <= new_component.second) {
            long long current_maximum = seg.RangeMaximumQuery(LR_bounds_old[ptr].first, LR_bounds_old[ptr].second);
            seg.RangeSumUpdate(LR_bounds_old[ptr].first, LR_bounds_old[ptr].second, -current_maximum);
            sum_of_maximums += current_maximum;
          } else if (new_component.second < LR_bounds_old[ptr].first) {
            break;
          }
        }
        seg.RangeSumUpdate(new_component.first, new_component.second, sum_of_maximums);
      }

      // Add StarDifference (Star[height][column] - Star[height - 1][column])
      for (auto &stars : StarDifference[height]) {
        int column = stars.first;
        int value = stars.second;
        seg.RangeSumUpdate(column, column, value);
      }
    }

    return SumAll() - seg.RangeMaximumQuery(1, N);
  }  

};

int main() {
  Constellation Solver;
  Solver.read();
  cout << Solver.solve() << "\n";
  return 0;
}

Compilation message

constellation3.cpp: In member function 'std::vector<std::vector<std::pair<int, int> > > Constellation::CalculateStarDifference()':
constellation3.cpp:212:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 1; j < stars_per_column[i].size(); j++) {
                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:218:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < stars_per_column[i].size(); j++) {
                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp: In member function 'long long int Constellation::solve()':
constellation3.cpp:338:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; ptr < LR_bounds_old.size(); ptr++) {
                ~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	6 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	6 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	5 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	6 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	6 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	5 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct
23	Correct	8 ms	768 KB	Output is correct
24	Correct	8 ms	768 KB	Output is correct
25	Correct	9 ms	768 KB	Output is correct
26	Correct	8 ms	768 KB	Output is correct
27	Correct	8 ms	768 KB	Output is correct
28	Correct	8 ms	768 KB	Output is correct
29	Correct	8 ms	768 KB	Output is correct
30	Correct	8 ms	768 KB	Output is correct
31	Correct	8 ms	768 KB	Output is correct
32	Correct	13 ms	768 KB	Output is correct
33	Correct	8 ms	768 KB	Output is correct
34	Correct	8 ms	768 KB	Output is correct
35	Correct	8 ms	768 KB	Output is correct
36	Correct	7 ms	768 KB	Output is correct
37	Correct	7 ms	768 KB	Output is correct
38	Correct	8 ms	768 KB	Output is correct
39	Correct	7 ms	720 KB	Output is correct
40	Correct	8 ms	768 KB	Output is correct
41	Correct	7 ms	768 KB	Output is correct
42	Correct	9 ms	768 KB	Output is correct
43	Correct	9 ms	768 KB	Output is correct
44	Correct	7 ms	640 KB	Output is correct

Subtask #3
65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	6 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	6 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	5 ms	384 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	5 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct
23	Correct	8 ms	768 KB	Output is correct
24	Correct	8 ms	768 KB	Output is correct
25	Correct	9 ms	768 KB	Output is correct
26	Correct	8 ms	768 KB	Output is correct
27	Correct	8 ms	768 KB	Output is correct
28	Correct	8 ms	768 KB	Output is correct
29	Correct	8 ms	768 KB	Output is correct
30	Correct	8 ms	768 KB	Output is correct
31	Correct	8 ms	768 KB	Output is correct
32	Correct	13 ms	768 KB	Output is correct
33	Correct	8 ms	768 KB	Output is correct
34	Correct	8 ms	768 KB	Output is correct
35	Correct	8 ms	768 KB	Output is correct
36	Correct	7 ms	768 KB	Output is correct
37	Correct	7 ms	768 KB	Output is correct
38	Correct	8 ms	768 KB	Output is correct
39	Correct	7 ms	720 KB	Output is correct
40	Correct	8 ms	768 KB	Output is correct
41	Correct	7 ms	768 KB	Output is correct
42	Correct	9 ms	768 KB	Output is correct
43	Correct	9 ms	768 KB	Output is correct
44	Correct	7 ms	640 KB	Output is correct
45	Correct	629 ms	43120 KB	Output is correct
46	Correct	667 ms	42596 KB	Output is correct
47	Correct	653 ms	42444 KB	Output is correct
48	Correct	622 ms	42988 KB	Output is correct
49	Correct	633 ms	41936 KB	Output is correct
50	Correct	619 ms	41776 KB	Output is correct
51	Correct	602 ms	42028 KB	Output is correct
52	Correct	607 ms	42980 KB	Output is correct
53	Correct	590 ms	42712 KB	Output is correct
54	Correct	592 ms	45696 KB	Output is correct
55	Correct	568 ms	44784 KB	Output is correct
56	Correct	545 ms	44096 KB	Output is correct
57	Correct	539 ms	43904 KB	Output is correct
58	Correct	321 ms	41160 KB	Output is correct
59	Correct	321 ms	41224 KB	Output is correct
60	Correct	536 ms	44092 KB	Output is correct
61	Correct	379 ms	40540 KB	Output is correct
62	Correct	540 ms	41804 KB	Output is correct
63	Correct	386 ms	40172 KB	Output is correct
64	Correct	391 ms	39352 KB	Output is correct
65	Correct	521 ms	41928 KB	Output is correct
66	Correct	362 ms	40056 KB	Output is correct

Submission #217167

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 21.0 / 21.0

Subtask #3 65.0 / 65.0

Subtask #1
14.0 / 14.0

Subtask #2
21.0 / 21.0

Subtask #3
65.0 / 65.0