Submission #1026992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026992		pudelos	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 KiB

rect

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define pi pair<int, int>
#define f first
#define s second
#define eb emplace_back
#define pb push_back
#define ll long long
#define V vector
const int maxn=2507, base=(1<<12), inf=1e9;

struct Blok {
  int lx, px, gy, dy;
};

V<Blok> bloki;

int n, m;
int A[maxn][maxn];
int gora[maxn][maxn], dol[maxn][maxn];
set<pi> przedzialy[maxn];

struct MinSegTree {
  int T[2*base];
  int query(int a, int b) {
    a+=base-1;
    b+=base+1;
    int minv=inf;
    while(a/2!=b/2) {
      if(a%2==0) minv=min(minv, T[a+1]);
      if(b%2==1) minv=min(minv, T[b-1]);
      a/=2; b/=2;
    }
    return minv;
  }
} DolSeg[maxn];
struct MaxSegTree {
  int T[2*base];
  int query(int a, int b) {
    a+=base-1;
    b+=base+1;
    int maxv=-inf;
    while(a/2!=b/2) {
      if(a%2==0) maxv=max(maxv, T[a+1]);
      if(b%2==1) maxv=max(maxv, T[b-1]);
      a/=2; b/=2;
    }
    return maxv;
  }
} GoraSeg[maxn];
struct SumSegTree {
  int T[2*base];
  void update(int v, int x) {
    v+=base;
    T[v]=x;
    v/=2;
    while(v>=1) {
      T[v]=T[2*v]+T[2*v+1];
      v/=2;
    }
  }
  int query(int a, int b) {
    a+=base-1;
    b+=base+1;
    int sum=0;
    while(a/2!=b/2) {
      if(a%2==0) sum+=T[a+1];
      if(b%2==1) sum+=T[b-1];
      a/=2; b/=2;
    }
    return sum;
  }
} SumSeg;
void generuj_gora_dol() {
  FOR(j, 1, m) {
    {
      stack<pi> stosik;
      FOR(i, 1, n) {
        pi x = {A[i][j], i};
        while(!stosik.empty() && stosik.top().f<x.f) stosik.pop();
        if(stosik.empty()) {
          gora[i][j]=-inf;
          stosik.push(x);
          continue;
        }
        gora[i][j]=stosik.top().s;
        stosik.push(x);
      }
    }

    {
      stack<pi> stosik;
      for(int i=n; i>=1; --i) {
        pi x = {A[i][j], i};
        while(!stosik.empty() && stosik.top().f<x.f) stosik.pop();
        if(stosik.empty()) {
          dol[i][j]=inf;
          stosik.push(x);
          continue;
        }
        dol[i][j]=stosik.top().s;
        stosik.push(x);
      }
    }
  }
}
void postaw_przedzialowce() {
  FOR(i, 1, n) {
    FOR(j, 0, 2*base-1) {
      GoraSeg[i].T[j]=-inf;
      DolSeg[i].T[j]=inf;
    }
    FOR(j, 1, m) {
      GoraSeg[i].T[j+base]=gora[i][j];
      DolSeg[i].T[j+base]=dol[i][j];
    }
    for(int j=base-1; j>=1; --j) {
      GoraSeg[i].T[j]=max(GoraSeg[i].T[2*j], GoraSeg[i].T[2*j+1]);
      DolSeg[i].T[j]=min(DolSeg[i].T[2*j], DolSeg[i].T[2*j+1]);
    }
  }
}
void znajdz_przedzialy_kazdemu_wierszowi() {
  FOR(i, 2, n-1) {
    {
      stack<int> stosik;
      FOR(j, 1, m) {
        while(!stosik.empty() && A[i][stosik.top()]<A[i][j]) stosik.pop();
        if(stosik.empty()) {
          stosik.push(j);
          continue;
        }
        int lewo = stosik.top();
        stosik.push(j);
        if(lewo+1<=j-1) przedzialy[i].insert({lewo+1, j-1});
      }
    }
    {
      stack<int> stosik;
      for(int j=m; j>=1; --j) {
        while(!stosik.empty() && A[i][stosik.top()]<A[i][j]) stosik.pop();
        if(stosik.empty()) {
          stosik.push(j);
          continue;
        }
        int prawo = stosik.top();
        stosik.push(j);
        if(j+1<=prawo-1) przedzialy[i].insert({j+1, prawo-1});
      }
    }
  }
}
void znajdz_bloki() {
  FOR(i, 2, n-1) {
    for(auto &[a, b] : przedzialy[i]) {
      FOR(j, i+1, n) {
        if(przedzialy[j].find({a, b})==przedzialy[j].end()) {
          bloki.pb({a, b, i, j-1});
          break;
        }
        przedzialy[j].erase({a, b});
      }
    }
  }
}

V<int> kub[maxn];

int rozw_blok(Blok &blok) {
  // cout << "blok: " << blok.lx << ' ' << blok.px << ' ' << blok.gy << ' ' << blok.dy << '\n';
  int sum=0;
  FOR(i, blok.gy, blok.dy) {
    for(int idx_do_wywalenia : kub[i]) SumSeg.update(idx_do_wywalenia, 0);
    kub[i].clear();

    int indexgorny = GoraSeg[i+1].query(blok.lx, blok.px);
    int indexdolny = DolSeg[i-1].query(blok.lx, blok.px);
    if(indexdolny>=i+1) {
      SumSeg.update(i, 1);
      if(indexdolny>blok.dy) kub[0].eb(i);
      else kub[indexdolny].eb(i);
    }

    if(indexgorny!=-inf) sum+=SumSeg.query(indexgorny+1, i);
    else sum+=SumSeg.query(0, i);
  }
  for(int idx_do_wywalenia : kub[0]) SumSeg.update(idx_do_wywalenia, 0);
  kub[0].clear();
  return sum;
}

int main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> m;
  FOR(i, 1, n) FOR(j, 1, m) cin>>A[i][j];

  generuj_gora_dol();
  postaw_przedzialowce();
  znajdz_przedzialy_kazdemu_wierszowi();
  znajdz_bloki();

  int res=0;
  for(Blok &blok : bloki) res+=rozw_blok(blok);
  cout << res << '\n';
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccjiy9mg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3yZQ5g.o:rect.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccjiy9mg.o: in function `main':
grader.cpp:(.text.startup+0x6fa): undefined reference to `count_rectangles(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status