Submission #987247

#	Time	Username	Problem	Language	Result	Execution time	Memory
987247		AdamGS	Rectangles (IOI19_rect)	C++17	0 / 100	174 ms	295864 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) {
      while(P.size()>0 && A[i][P.back()]<A[i][j]) {
        P.pop_back();
        if(P.size()) 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) {
      while(P.size()>0 && A[P.back()][j]<A[i][j]) {
        P.pop_back();
        if(P.size()) 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;
  for(int i=1; i<n-1; ++i) 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:24:7: note: in expansion of macro 'rep'
   24 |       rep(a, lewo[i][j].size()) {
      |       ^~~
rect.cpp:25: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]
   25 |         while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:26: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]
   26 |         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:40:7: note: in expansion of macro 'rep'
   40 |       rep(a, gora[i][j].size()) {
      |       ^~~
rect.cpp:41: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]
   41 |         while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:42: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]
   42 |         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: 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