제출 #212651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212651		rama_pang	별자리 3 (JOI20_constellation3)	C++14	100 / 100	616 ms	45448 KiB

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 Full_Solution {

 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() {
  Full_Solution Solver;
  Solver.read();
  cout << Solver.solve() << "\n";
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In member function 'std::vector<std::vector<std::pair<int, int> > > Full_Solution::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 Full_Solution::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 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65