Submission #248537

#	Time	Username	Problem	Language	Result	Execution time	Memory
248537		quocnguyen1012	Rectangles (IOI19_rect)	C++14	100 / 100	1669 ms	215484 KiB

rect

#ifndef LOCAL
#include "rect.h"
#endif // LOCAL
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2505;

int N, M;
vector<int> strow[maxn], stcol[maxn];
int lst_row[maxn][maxn], lst_col[maxn][maxn];
int cnt_row[maxn][maxn], cnt_col[maxn][maxn];
int bit[maxn];

void upd(int i, int v)
{
  for(; i < maxn; i += i & -i)
    bit[i] += v;
}

int sum(int i)
{
  int res = 0;
  for(; i; i -= i & -i)
    res += bit[i];
  return res;
}

ii get(int l, int r, int cur, int lst[maxn][maxn], int cnt[maxn][maxn])
{
  if(lst[l][r] != cur - 1)
    cnt[l][r] = 0;
  ++cnt[l][r]; lst[l][r] = cur;
  return mp(r - l - 1, cnt[l][r]);
}

ll way(vector<ii> & row, vector<ii> & col)
{
  for(auto & it : col) swap(it.fi, it.se);
  ll res = 0;
  sort(col.rbegin(), col.rend());
  sort(row.rbegin(), row.rend());
  int j = 0;
  for(int i = 0; i < (int)row.size(); ++i){
    while(j < (int)col.size() && col[j].fi >= row[i].fi){
      upd(col[j].se, 1);
      ++j;
    }
    res += sum(row[i].se);
  }
  for(int i = 0; i < j; ++i)
    upd(col[i].se, -1);
  return res;
}

long long count_rectangles(std::vector<std::vector<int>> a)
{
  N = a.size();
  M = a[0].size();
  for(int i = 0; i < N; ++i)
    strow[i].eb(0);
  for(int j = 0; j < M; ++j)
    stcol[j].eb(0);
  ll ans = 0;
  for(int i = 0; i < N - 1; ++i){
    for(int j = 0; j < M - 1; ++j){
      ///row
      vector<ii> rows;
      bool eq = false;
      while(strow[i].size()){
        int k = strow[i].back();
        if(k < j && !eq) rows.eb(get(k, j + 1, i, lst_row, cnt_row));
        if(a[i][k] == a[i][j + 1]) eq = true;
        if(a[i][k] <= a[i][j + 1])
          strow[i].pop_back();
        else break;
      }
      strow[i].eb(j + 1);
      ///col
      vector<ii> cols;
      eq = false;
      while(stcol[j].size()){
        int k = stcol[j].back();
        //if(i == 4 && j == 3) cerr << k << ' ';
        if(k < i && !eq) cols.eb(get(k, i + 1, j, lst_col, cnt_col));
        if(a[i + 1][j] == a[k][j]) eq = true;
        if(a[k][j] <= a[i + 1][j])
          stcol[j].pop_back();
        else break;
      }
      stcol[j].eb(i + 1);
      /*
      if(i == 4 && j == 3){
        for(auto & it : rows) cerr << it.fi << ' ' << it.se << '\n';
        cerr << '\n';
        for(auto & it : cols) cerr << it.fi << ' ' << it.se << '\n';
        cerr << way(rows, cols);
      }
      */
      auto v = way(rows, cols);
      ans += v;
      if(v){
       // cerr << i + 1 << ' ' << j + 1 << ' ' << v << '\n';
      }
    }
  }
  return ans;
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int n, m; cin >> n >> m;
  vector<vector<int>> a;
  a.assign(n, vector<int>(m));
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      cin >> a[i][j];
    }
  }
  cout << count_rectangles(a);
}
#endif

• 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