Submission #1215766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215766		Gabp	Rectangles (IOI19_rect)	C++20	72 / 100	4017 ms	1107732 KiB

rect

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

const int N = 2505;

struct SegTree {
  int st[4 * N];
  
  SegTree(int n) {
    for (int i = 0; i < 4 * n; i++) st[i] = 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();
  
  unordered_map<int,int> dp_row[N][N];
  vector<int> dp_col[N][N];
  
  for (int i = 0; i < n; i++) {
    set<int> row;
    row.insert(-1);
    row.insert(m);
    
    vector<tuple<int,int,int>> b;
    for (int j = 0; j < m; j++) b.emplace_back(-a[i][j], i, j);
    sort(b.begin(), b.end());
    
    int p = 0;
    while (p < m) {
      int curr = get<0>(b[p]);
      int start = p;
      while (p < m && get<0>(b[p]) == curr) {
        auto [_, x, y] = b[p++];
        row.insert(y);
      }
      
      for (int j = start; j < p; j++) {
        auto [_, x, y] = b[j];
        auto it = row.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;
        }
      }
    }
  }
  
  for (int i = 0; i < m; i++) {
    set<int> col;
    col.insert(-1);
    col.insert(n);
    
    vector<tuple<int,int,int>> b;
    for (int j = 0; j < n; j++) b.emplace_back(-a[j][i], j, i);
    sort(b.begin(), b.end());
    
    int p = 0;
    while (p < n) {
      int curr = get<0>(b[p]);
      int start = p;
      while (p < n && get<0>(b[p]) == curr) {
        auto [_, x, y] = b[p++];
        col.insert(x);
      }
      
      for (int j = start; j < p; j++) {
        auto [_, x, y] = b[j];
        auto it = col.find(x);
        it--;
        if (*it != -1 && x - *it > 1) {
          int l = (*it) + 1;
          int r = x - 1;
          dp_col[l][y].push_back(-r);
        }
        it++;
        it++;
        if (*it != n && (*it) - x > 1) {
          int l = x + 1;
          int r = (*it) - 1;
          dp_col[l][y].push_back(-r);
        }
      }
    }
  }
  
  SegTree st(m);
  long long int ans = 0;
  for (int i = n - 2; i > 0; i--) {
    map<int,int> nxt;
    
    for (int j = m - 2; j > 0; j--) {
      map<int,int> curr;
      for (auto idx: dp_col[i][j]) {
        curr[idx] = j;
      }
      
      if (j + 2 < m) {
        for (auto [idx, _]: curr) {
          if (nxt.count(idx)) curr[idx] = nxt[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]: curr) {
        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);
      
      nxt = move(curr);
    }
  }
  
  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: 0 / 28