Submission #824779

#	Time	Username	Problem	Language	Result	Execution time	Memory
824779		erray	Rectangles (IOI19_rect)	C++17	100 / 100	2092 ms	834552 KiB

rect

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

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

struct Fenwick {
  vector<short> sum;
  int n;
  Fenwick(int _n) : n(_n) {
    sum.resize(n + 1);
  }
  void modify(int x, int d) {
    x += 1;
    while (x <= n) {
      sum[x] += d;
      x += x & -x;
    }
  }
  int get(int x) {
    x += 1;
    int res = 0;
    while (x > 0) {
      res += sum[x];
      x -= x & -x;
    }
    return res;
  }
};

constexpr int mxN = 2500;
vector<array<short, 2>> col_ranges[mxN][mxN];
vector<array<short, 2>> row_ranges[mxN][mxN];
using RT = vector<vector<vector<array<short, 2>>>>;
void calc_ranges(vector<vector<int>> A, bool inv) {
	int N = int(A.size());
  int M = int(A[0].size());
  int sn = N, sm = M;
  if (inv) {
    swap(sn, sm);
  }
  //RT res(sn, vector<vector<array<short, 2>>>(sm));
  vector<vector<array<int, 2>>> last(M, vector<array<int, 2>>(M, array<int, 2>{}));
  for (int i = N - 1; i >= 0; --i) {
    auto Add = [&](int l, int r) {
      if (l + 1 == r) {
        return;
      }
      if (last[l][r][0] != i + 1) {
        last[l][r][1] = i;
      }
      last[l][r][0] = i;
      (inv ? col_ranges[l][i] : row_ranges[i][l]).push_back({r, last[l][r][1]});
    };
    vector<int> st;
    for (int j = M - 1; j >= 0; --j) {
      bool eq = false;
      while (!st.empty() && A[i][st.back()] <= A[i][j]) {
        eq |= A[i][st.back()] == A[i][j];
        Add(j, st.back());
        st.pop_back();
      }
      if (!st.empty() && !eq) {
        Add(j, st.back());
      }
      st.push_back(j);
    }
  }
}

long long count_rectangles(std::vector<std::vector<int> > A) {
	int N = int(A.size());
  int M = int(A[0].size());
  calc_ranges(A, false);  
  vector<vector<int>> temp_A(M, vector<int>(N));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      temp_A[j][i] = A[i][j];
    }
  }
  calc_ranges(temp_A, true);
  /*
  auto temp = calc_ranges(temp_A);
  RT col_ranges(N, vector<vector<array<short, 2>>>(M));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      col_ranges[i][j] = temp[j][i];
    }
  }
  */
  vector<Fenwick> fenw(N, Fenwick(N));
  long long ans = 0;
  for (int l = 0; l < M - 1; ++l) {
    vector<vector<array<short, 2>>> query(M);
    for (int i = 0; i < N; ++i) {
      for (auto[r, ending] : row_ranges[i][l]) {
        query[r].push_back({i, ending});
      }
    }
    vector<vector<array<short, 2>>> rem(M);
    for (int i = 0; i < N; ++i) {
      for (auto[d, ending] : col_ranges[i][l + 1]) {
        fenw[i + 1].modify(d - 1, +1);
        rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
      }
    }
    for (int r = l + 2; r < M; ++r) {
      for (auto[u, d] : query[r]) {
        ans += fenw[u].get(d);
      }
      for (auto[u, d] : rem[r]) {
        fenw[u].modify(d, -1);
      }
    }
    debug(ans);
  }
  return ans;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:58:62: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   58 |       (inv ? col_ranges[l][i] : row_ranges[i][l]).push_back({r, last[l][r][1]});
      |                                                              ^
rect.cpp:58:79: warning: narrowing conversion of '(&(&(& last)->std::vector<std::vector<std::array<int, 2> > >::operator[](((std::vector<std::vector<std::array<int, 2> > >::size_type)l)))->std::vector<std::array<int, 2> >::operator[](((std::vector<std::array<int, 2> >::size_type)r)))->std::array<int, 2>::operator[](1)' from 'std::array<int, 2>::value_type' {aka 'int'} to 'short int' [-Wnarrowing]
   58 |       (inv ? col_ranges[l][i] : row_ranges[i][l]).push_back({r, last[l][r][1]});
      |                                                                               ^
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:102:29: warning: narrowing conversion of 'i' from 'int' to 'short int' [-Wnarrowing]
  102 |         query[r].push_back({i, ending});
      |                             ^
rect.cpp:109:50: warning: narrowing conversion of '(i + 1)' from 'int' to 'short int' [-Wnarrowing]
  109 |         rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
      |                                                ~~^~~
rect.cpp:109:57: warning: narrowing conversion of '(((int)d) - 1)' from 'int' to 'short int' [-Wnarrowing]
  109 |         rem[min(M - 1, ending + 1)].push_back({i + 1, d - 1});
      |                                                       ~~^~~

• 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