Submission #987251

#	Time	Username	Problem	Language	Result	Execution time	Memory
987251		AdamGS	Rectangles (IOI19_rect)	C++17	100 / 100	2058 ms	625332 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;
int tr[4*LIM], N=1;
vector<pair<int,int>>lewo[LIM][LIM], gora[LIM][LIM];
void upd(int v) {
  v+=N;
  while(v) {
    ++tr[v];
    v/=2;
  }
}
void upd2(int v) {
  v+=N;
  while(v) {
    --tr[v];
    v/=2;
  }
}
int cnt(int v) {
  v+=N;
  int ans=tr[v];
  while(v) {
    if(v&1) ans+=tr[v-1];
    v/=2;
  }
  return ans;
}
ll count_rectangles(vector<vector<int>>A) {
  int n=A.size(), m=A[0].size();
  while(N<max(n, m)) N*=2;
  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) rep(j, m) {
    rep(l, lewo[i][j].size()) swap(lewo[i][j][l].st, lewo[i][j][l].nd);
    sort(all(lewo[i][j]));
  }
  rep(i, n-1) rep(j, m-1) {
    int b=(int)lewo[i][j+1].size()-1;
    for(int a=(int)gora[i+1][j].size()-1; a>=0; --a) {
      while(b>=0 && lewo[i][j+1][b].st>=gora[i+1][j][a].st) {
        upd(lewo[i][j+1][b].nd);
        --b;
      }
      ans+=(ll)cnt(gora[i+1][j][a].nd);
    }
    ++b;
    while(b<lewo[i][j+1].size()) {
      upd2(lewo[i][j+1][b].nd);
      ++b;
    }
  }
  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:51:7: note: in expansion of macro 'rep'
   51 |       rep(a, lewo[i][j].size()) {
      |       ^~~
rect.cpp:52: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]
   52 |         while(l<lewo[i-1][j].size() && lewo[i-1][j][l].st<lewo[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:53: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]
   53 |         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:69:7: note: in expansion of macro 'rep'
   69 |       rep(a, gora[i][j].size()) {
      |       ^~~
rect.cpp:70: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]
   70 |         while(l<gora[i][j-1].size() && gora[i][j-1][l].st<gora[i][j][a].st) ++l;
      |               ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:71: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]
   71 |         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;
      |            ~^~~~~~~~~~~~~~~~~~~~
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:77:5: note: in expansion of macro 'rep'
   77 |     rep(l, lewo[i][j].size()) swap(lewo[i][j][l].st, lewo[i][j][l].nd);
      |     ^~~
rect.cpp:90:12: 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 |     while(b<lewo[i][j+1].size()) {
      |           ~^~~~~~~~~~~~~~~~~~~~

• 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