Submission #1215742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215742		Gabp	Rectangles (IOI19_rect)	C++20	59 / 100	4937 ms	1114112 KiB

rect

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

struct SegTree {
  vector<int> st;
  
  SegTree(int n) {
    st.assign(4 * n, 0);
  }
  
  void update(int v, int tl, int tr, int idx, int add) {
    if (tl == tr) {
      st[v] += add;
      return;
    }
    
    int mid = tl + (tr - tl) / 2;
    if (idx <= mid) update(2 * v, tl, mid, idx, add);
    else update(2 * v + 1, mid + 1, tr, idx, add);
    st[v] = st[2 * v] + st[2 * v + 1];
  }
  
  int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) return st[v];
    
    int mid = tl + (tr - tl) / 2;
    return query(2 * v, tl, mid, l, min(mid, r)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r);
  }
};

long long int count_rectangles(vector<vector<int>> a) {
  int n = a.size();
  int m = a[0].size();
  
  vector<set<int>> row(n), col(m);
  vector<vector<map<int,int>>> dp_row(n, vector<map<int,int>>(m));
  vector<vector<map<int,int>>> dp_col = dp_row;
  
  vector<tuple<int,int,int>> b;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      b.emplace_back(-a[i][j], i, j);
    }
  }
  sort(b.begin(), b.end());
  
  for (int i = 0; i < n; i++) {
    row[i].insert(-1);
    row[i].insert(m);
  }
  for (int i = 0; i < m; i++) {
    col[i].insert(-1);
    col[i].insert(n);
  }
  
  int p = 0;
  while (p < n * m) {
    int curr = get<0>(b[p]);
    int start = p;
    while (p < n * m && get<0>(b[p]) == curr) {
      auto [_, i, j] = b[p++];
      row[i].insert(j);
      col[j].insert(i);
    }
    
    for (int i = start; i < p; i++) {
      auto [_, x, y] = b[i];
      
      // row
      {
        auto it = row[x].find(y);
        it--;
        if (*it != -1 && y - *it > 1) {
          int l = (*it) + 1;
          int r = y - 1;
          dp_row[x][l][r] = -x;
        }
        it++;
        it++;
        if (*it != m && (*it) - y > 1) {
          int l = y + 1;
          int r = (*it) - 1;
          dp_row[x][l][r] = -x;
        }
      }
      
      // col
      {
        auto it = col[y].find(x);
        it--;
        if (*it != -1 && x - *it > 1) {
          int l = (*it) + 1;
          int r = x - 1;
          dp_col[l][y][-r] = y;
        }
        it++;
        it++;
        if (*it != n && (*it) - x > 1) {
          int l = x + 1;
          int r = (*it) - 1;
          dp_col[l][y][-r] = y;
        }
      }
    }
  }
  
  SegTree st(m);
  long long int ans = 0;
  for (int i = n - 2; i > 0; i--) {
    for (int j = m - 2; j > 0; j--) {
      if (j + 2 < m) {
        for (auto [idx, _]: dp_col[i][j]) {
          if (dp_col[i][j + 1].count(idx)) dp_col[i][j][idx] = dp_col[i][j + 1][idx];
        }
      }
      
      vector<pair<int,int>> order;
      for (auto [idx, _]: dp_row[i][j]) {
        if (i + 2 < n && dp_row[i + 1][j].count(idx)) dp_row[i][j][idx] = dp_row[i + 1][j][idx];
        order.emplace_back(dp_row[i][j][idx], idx);
      }
      sort(order.begin(), order.end());
      
      int p = 0;
      for (auto [idx, r]: dp_col[i][j]) {
        while (p < order.size() && order[p].first <= idx) {
          st.update(1, 0, m - 1, order[p++].second, 1);
        }
        
        ans += st.query(1, 0, m - 1, j, r);
      }
      while (--p >= 0) st.update(1, 0, m - 1, order[p].second, -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: 0 / 13
• Subtask 7: 0 / 28