Submission #223688

#	Time	Username	Problem	Language	Result	Execution time	Memory
223688		rama_pang	Rectangles (IOI19_rect)	C++14	100 / 100	4261 ms	880088 KiB

rect

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

class FenwickTree {
 private:
  int sz;
  vector<int> tree;

 public:
  FenwickTree() {}
  FenwickTree(int n) : sz(n) { tree.assign(sz, 0); }

  void Update(int p, int x) {
    for (int i = p + 1; i <= sz; i += (i & -i)) {
      tree[i - 1] += x;
    }
  }

  int Query(int p) {
    int res = 0;
    for (int i = p + 1; i > 0; i -= (i & -i)) {
      res += tree[i - 1];
    }
    return res;
  }
};

struct event_t {
  int type;
  int r2, c2;
  event_t() {}
  event_t(int t, int r, int c) : type(t), r2(r), c2(c) {}
  bool operator < (const event_t &o) const {
    return make_pair(r2, type) < make_pair(o.r2, o.type);
  }
};

vector<pair<int, int>> get_pairs(vector<int> a) {
  int n = a.size();
  vector<int> L(n, -1), R(n, n);

  { // Find the nearest value greater than a[i] on its left and right
    stack<int> s;
    for (int i = 0; i < n; i++) {
      while (!s.empty() && a[s.top()] <= a[i]) s.pop();
      if (!s.empty()) L[i] = s.top();
      s.emplace(i);
    }

    while (!s.empty()) s.pop();
    for (int i = n - 1; i >= 0; i--) {
      while (!s.empty() && a[s.top()] <= a[i]) s.pop();
      if (!s.empty()) R[i] = s.top();
      s.emplace(i);
    }
  }

  vector<pair<int, int>> pairs; // valid pairs
  for (int i = 0; i < n; i++) {
    if (L[i] == -1 || R[i] == n) continue;
    pairs.emplace_back(L[i] + 1, R[i] - 1);
  }

  sort(begin(pairs), end(pairs));
  pairs.resize(unique(begin(pairs), end(pairs)) - begin(pairs));

  return pairs;
}

long long count_rectangles(vector<vector<int>> a) {
  int n = a.size(), m = a[0].size();
  long long ans = 0;

  // valid pairs where (i, j) is one of its cell in the pairs
  vector<vector<vector<int>>> go_r(n, vector<vector<int>>(m));
  vector<vector<vector<int>>> go_d(n, vector<vector<int>>(m));

  { // Find valid pairs for each row and column
    // Find valid pairs in each row
    for (int i = 1; i < n - 1; i++) {
      vector<pair<int, int>> pairs = get_pairs(a[i]);
      for (auto j : pairs) {
        go_r[i][j.first].emplace_back(j.second);
      }
    }

    // Find valid pairs in each column
    for (int i = 1; i < m - 1; i++) {
      vector<int> cur;
      for (int j = 0; j < n; j++) {
        cur.emplace_back(a[j][i]);
      }
      vector<pair<int, int>> pairs = get_pairs(cur);
      for (auto j : pairs) {
        go_d[j.first][i].emplace_back(j.second);
      }
    }
  }

  // how many valid pairs (c1, c2) in the bottomside of current row
  vector<vector<pair<int, int>>> span_r(m, vector<pair<int, int>>(m, {-1, -1})); // (row start, row end)

  // how many valid pairs (r1, r2) in the rightside of current column
  vector<vector<pair<int, int>>> span_d(n, vector<pair<int, int>>(n, {-1, -1})); // (column start, column end)

  FenwickTree BIT(m);

  for (int r1 = n - 1; r1 >= 0; r1--) {
    for (int c1 = m - 1; c1 >= 0; c1--) {
      sort(begin(go_r[r1][c1]), end(go_r[r1][c1]));
      sort(begin(go_d[r1][c1]), end(go_d[r1][c1]));

      { // Process valid pairs which originated from (r1, c1)
        for (auto c2 : go_r[r1][c1]) {
          if (span_r[c1][c2].first == r1 + 1) { // we can extend
            span_r[c1][c2].first = r1;
          } else { // we must start anew
            span_r[c1][c2] = {r1, r1};
          }
        }

        for (auto r2 : go_d[r1][c1]) {
          if (span_d[r1][r2].first == c1 + 1) { // we can extend
            span_d[r1][r2].first = c1;
          } else { // we must start anew
            span_d[r1][r2] = {c1, c1};
          }
        }
      }

      vector<event_t> events; // (type, (r2, c2)) type = 0 for insertion, type = 1 for query
      { // Process each valid pair sorted by r2
        for (auto r2 : go_d[r1][c1]) {
          events.emplace_back(0, r2, span_d[r1][r2].second);
        }
        for (auto c2 : go_r[r1][c1]) {
          events.emplace_back(1, span_r[c1][c2].second, c2);
        }
        sort(begin(events), end(events));
      }

      for (auto event : events) {
        if (event.type == 0) { // insert new column valid pair
          BIT.Update(event.c2, +1);
        } else { // query for number of rectangles current row valid pair can form with
          ans += BIT.Query(m - 1) -  BIT.Query(event.c2 - 1);
        }
      }

      // Undo all updates
      for (auto event : events) {
        if (event.type == 0) {
          BIT.Update(event.c2, -1);
        }
      }
    }
  }

  return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28