Submission #173755

#	Time	Username	Problem	Language	Result	Execution time	Memory
173755		AlexLuchianov	Rectangles (IOI19_rect)	C++14	0 / 100	5086 ms	465496 KiB

rect

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 2500;
int v[1 + nmax][1 + nmax];
int n, m;

namespace Dsu{
std::vector<int> mult;
std::vector<int> sz;
std::vector<int> maxid;
std::vector<int> minid;
void initialize(int n){
  mult.resize(1 + n);
  sz.resize(1 + n);
  maxid.resize(1 + n);
  minid.resize(1 + n);
  for(int i = 1;i <= n; i++){
    minid[i] = maxid[i] = mult[i] = i;
    sz[i] = 1;
  }
}

int jump(int gala){
  if(gala != mult[gala])
    mult[gala] = jump(mult[gala]);
  return mult[gala];
}

void unite(int gala, int galb){
  gala = jump(gala);
  galb = jump(galb);
  if(gala == galb)
    return ;
  if(sz[galb] < sz[gala])
    std::swap(gala, galb);
  sz[galb] += sz[gala];
  mult[gala] = galb;
  maxid[galb] = MAX(maxid[gala], maxid[galb]);
  minid[galb] = MIN(minid[gala], minid[galb]);
}

}

std::vector<int> orizontal[1 + nmax][1 + nmax];
std::vector<int> vertical[1 + nmax][1 + nmax];

std::map<std::tuple<int,int,int>, int> freq;

struct Update{
  int type;
  int x;
  int y;
  int time;
  bool operator < (Update const &a) const{
    if(time != a.time)
      return time < a.time;
    else
      return type < a.type;
  }
};

int scount[1 + nmax][1 + (int)sqrt(nmax)];

ll solvelevel(int level){
  std::map<std::pair<int,int>, int> freq2;

  std::vector<Update> updates;
  //std::cout << "Solve: " << level << '\n';
  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < orizontal[level][i].size(); h++){
      int lim = orizontal[level][i][h];
      freq[std::make_tuple(level, i, lim)] = freq[std::make_tuple(level + 1, i, lim)] + 1;
      updates.push_back({1, i, lim, -freq[std::make_tuple(level, i, lim)]});
      //std::cout << ":";
    }
  }

  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < vertical[level][i].size(); h++){
      int lim = vertical[level][i][h];
      freq2[{i, lim}] = freq2[{i - 1, lim}] + 1;
    }
  }

  //std::cout << "verticals:\n";
  for(int i = 1;i < m - 1; i++){
    for(int h = 0; h < vertical[level][i].size(); h++){
      int lim = vertical[level][i][h];
     //  std::cout << level << " " << i << " " << vertical[level][i][h] << "| ";
      if(0 == freq2[{i + 1, lim}]){
        updates.push_back({2, i - freq2[{i, lim}] + 1, i, -(lim - level + 1) });
      }
    }
  }
  //std::cout << ":";
  sort(updates.begin(), updates.end());

  std::vector<Update> onlyupdates;

  int rad = sqrt(m);
  ll result = 0;

  for(int i = 1;i <= m; i++)
    for(int j = 0; j <= rad; j++)
      scount[i][0] = 0;

 // std::cout << vertical[28][20].size() << '\n';

  for(int i = 0; i < updates.size(); i++){
    Update curr = updates[i];
    //std::cout << curr.type << " " << curr.x << " " << curr.y << " " << -curr.time<< '\n';
    if(curr.type == 1){
      onlyupdates.push_back(curr);
      int x = curr.x, y = curr.y;
      while(1 <= x){
        scount[x][y - x]++;
        x--;
      }
    } else {
      if((curr.y - curr.x) <= rad){
        for(int j = curr.x; j <= curr.y; j++)
          result += scount[curr.x][j - curr.x];
      } else {
        for(int j = 0; j < onlyupdates.size(); j++){
          if(curr.x <= onlyupdates[j].x && onlyupdates[j].y <= curr.y)
            result++;
        }
      }
    }
  }

  //std::cout << level << " " << result << '\n';
  return result;
}

long long count_rectangles(std::vector<std::vector<int> > a){
  n = a.size();
  m = a[0].size();
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      v[i][j] = a[i][j];
  for(int i = 1; i < n - 1; i++){
    std::vector<std::pair<int,int>> temp;
    for(int j = 1;j < m - 1; j++)
      temp.push_back({v[i][j], j});
    sort(temp.begin(), temp.end());
    Dsu::initialize(m);
    for(int j = 0; j < temp.size(); j++){
      int pos = temp[j].second;
      if(v[i][pos - 1] <= v[i][pos])
        Dsu::unite(pos - 1, pos);
      if(v[i][pos + 1] < v[i][pos])
        Dsu::unite(pos + 1, pos);
      int x = Dsu::minid[Dsu::jump(pos)], y = Dsu::maxid[Dsu::jump(pos)];
      if(v[i][x - 1] > v[i][pos] && v[i][pos] < v[i][y + 1])
        orizontal[i][x].push_back(y);
    }
  }

  for(int i = 1; i < m - 1; i++){
    std::vector<std::pair<int,int>> temp;
    for(int j = 1;j < n - 1; j++)
      temp.push_back({v[j][i], j});
    sort(temp.begin(), temp.end());
    Dsu::initialize(n);
    for(int j = 0; j < temp.size(); j++){
      int pos = temp[j].second;
      if(v[pos - 1][i] <= v[pos][i])
        Dsu::unite(pos - 1, pos);
      if(v[pos + 1][i] < v[pos][i])
        Dsu::unite(pos + 1, pos);
      int x = Dsu::minid[Dsu::jump(pos)], y = Dsu::maxid[Dsu::jump(pos)];
      //std::cout << i << " " << x << " " << y << '\n';
      if(v[x - 1][i] > v[pos][i] && v[pos][i] < v[y + 1][i])
        vertical[x][i].push_back(y);
    }
  }
  ll result = 0;
  for(int i = n - 2; 1 <= i; i--)
    result += solvelevel(i);
  return result;
}

Compilation message (stderr)

rect.cpp: In function 'll solvelevel(int)':
rect.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < orizontal[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < vertical[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < vertical[level][i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < updates.size(); i++){
                  ~~^~~~~~~~~~~~~~~~
rect.cpp:131:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < onlyupdates.size(); j++){
                        ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:155:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < temp.size(); j++){
                    ~~^~~~~~~~~~~~~
rect.cpp:173:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < temp.size(); j++){
                    ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28