Submission #296984

#	Time	Username	Problem	Language	Result	Execution time	Memory
296984		AlexLuchianov	Rectangles (IOI19_rect)	C++14	100 / 100	3563 ms	746028 KiB

rect

#include "rect.h"
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 2500;
std::vector<std::pair<int,int>> down[1 + nmax][1 + nmax];
std::vector<std::pair<int,int>> right[1 + nmax][1 + nmax];

class FenwickTree{
private:
  std::vector<int> aib;
  int n;
public:
  FenwickTree(int n_) {
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val) {
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] += val;
  }
  int query(int pos) {
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result;
  }
};

struct Event{
  int type;
  int time;
  int val;
  bool operator < (Event const &a) const {
    if(time != a.time)
      return time > a.time;
    else
      return type < a.type;
  }
};

long long count_rectangles(std::vector<std::vector<int>> v) {
	int n = v.size();
  int m = v[0].size();
  for(int i = 0; i < n; i++) {
    std::stack<int> st;
    for(int j = m - 1; 0 <= j; j--) {
      while(0 < st.size() && v[i][st.top()] < v[i][j]) {
        if(j + 1 <= st.top() - 1)
          right[i][j + 1].push_back({st.top() - 1 - j, 1});
        st.pop();
      }
      if(0 < st.size()) {
        if(j + 1 <= st.top() - 1)
          right[i][j + 1].push_back({st.top() - 1 - j, 1});
        if(v[i][st.top()] == v[i][j])
          st.pop();
      }
      st.push(j);
    }
  }
  for(int i = 0; i < m; i++) {
    std::stack<int> st;
    for(int j = n - 1; 0 <= j; j--) {
      while(0 < st.size() && v[st.top()][i] < v[j][i]) {
        if(j + 1 <= st.top() - 1)
          down[j + 1][i].push_back({st.top() - 1 - j, 1});
        st.pop();
      }
      if(0 < st.size()) {
        if(j + 1 <= st.top() - 1)
          down[j + 1][i].push_back({st.top() - 1 - j, 1});
        if(v[st.top()][i] == v[j][i])
          st.pop();
      }
      st.push(j);
    }
  }

  for(int i = n - 1; 0 <= i; i--) {
    for(int j = m - 1; 0 <= j; j--) {
      for(int h = 0; h < right[i][j].size(); h++) {
        std::pair<int,int> &el = right[i][j][h];
        std::vector<std::pair<int,int>>::iterator it = std::lower_bound(right[i + 1][j].begin(), right[i + 1][j].end(), el);
        if(it != right[i + 1][j].end() && it->first == el.first) {
          el.second = it->second + 1;
        }
      }
      for(int h = 0; h < down[i][j].size(); h++) {
        std::pair<int,int> &el = down[i][j][h];
        std::vector<std::pair<int,int>>::iterator it = std::lower_bound(down[i][j + 1].begin(), down[i][j + 1].end(), el);
        if(it != down[i][j + 1].end() && it->first == el.first)
          el.second = it->second + 1;
      }
    }
  }
  FenwickTree aib(nmax);
  ll result = 0;
  for(int i = 1; i <= n - 2; i++) {
    for(int j = 1;j <= m - 2; j++) {
      std::vector<Event> events;
      for(int h = 0; h < right[i][j].size(); h++)
        events.push_back({2, right[i][j][h].first, right[i][j][h].second});
      for(int h = 0; h < down[i][j].size(); h++)
        events.push_back({1, down[i][j][h].second, down[i][j][h].first});
      std::sort(events.begin(), events.end());
      for(int h = 0; h < events.size(); h++) {
        if(events[h].type == 1)
          aib.update(events[h].val, 1);
        else
          result += aib.query(events[h].val);
      }
      for(int h = 0; h < events.size(); h++)
        if(events[h].type == 1)
          aib.update(events[h].val, -1);
    }
  }
  return result;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |       for(int h = 0; h < right[i][j].size(); h++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       for(int h = 0; h < down[i][j].size(); h++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |       for(int h = 0; h < right[i][j].size(); h++)
      |                      ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |       for(int h = 0; h < down[i][j].size(); h++)
      |                      ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:115:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |       for(int h = 0; h < events.size(); h++) {
      |                      ~~^~~~~~~~~~~~~~~
rect.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |       for(int h = 0; h < events.size(); h++)
      |                      ~~^~~~~~~~~~~~~~~

• 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