Submission #987248

#	Time	Username	Problem	Language	Result	Execution time	Memory
987248		AdamGS	Rectangles (IOI19_rect)	C++17	100 / 100	4062 ms	625396 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2507;
vector<pair<int,int>>lewo[LIM][LIM], gora[LIM][LIM];
ll count_rectangles(vector<vector<int>>A) {
  int n=A.size(), m=A[0].size();
  rep(i, n) {
    vector<int>P;
    rep(j, m) {
      int lst=-1;
      while(P.size()>0 && A[i][P.back()]<A[i][j]) {
        lst=A[i][P.back()];
        P.pop_back();
        if(P.size() && A[i][P.back()]!=lst) lewo[i][j].pb({j-P.back()-1, 1});
      }
      P.pb(j);
      if(!i) continue;
      int l=0;
      rep(a, lewo[i][j].size()) {
        while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
        if(l<lewo[i-1][j].size() && lewo[i-1][j][l].st==lewo[i][j][a].st) lewo[i][j][a].nd+=lewo[i-1][j][l].nd;
      }
    }
  }
  rep(j, m) {
    vector<int>P;
    rep(i, n) {
      int lst=-1;
      while(P.size()>0 && A[P.back()][j]<A[i][j]) {
        lst=A[P.back()][j];
        P.pop_back();
        if(P.size() && lst!=A[P.back()][j]) gora[i][j].pb({i-P.back()-1, 1});
      }
      P.pb(i);
      if(!j) continue;
      int l=0;
      rep(a, gora[i][j].size()) {
        while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
        if(l<gora[i][j-1].size() && gora[i][j-1][l].st==gora[i][j][a].st) gora[i][j][a].nd+=gora[i][j-1][l].nd;
      }
    }
  }
  ll ans=0;
  rep(i, n-1) rep(j, m-1) {
    for(auto a : lewo[i][j+1]) {
      for(auto b : gora[i+1][j]) {
        if(a.nd>=b.st && b.nd>=a.st) ++ans;
      }
    }
  }
  return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
rect.cpp:26:7: note: in expansion of macro 'rep'
   26 |       rep(a, lewo[i][j].size()) {
      |       ^~~
rect.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if(l<lewo[i-1][j].size() && lewo[i-1][j][l].st==lewo[i][j][a].st) lewo[i][j][a].nd+=lewo[i-1][j][l].nd;
      |            ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
rect.cpp:44:7: note: in expansion of macro 'rep'
   44 |       rep(a, gora[i][j].size()) {
      |       ^~~
rect.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(l<gora[i][j-1].size() && gora[i][j-1][l].st==gora[i][j][a].st) gora[i][j][a].nd+=gora[i][j-1][l].nd;
      |            ~^~~~~~~~~~~~~~~~~~~~

• 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