Submission #1021097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021097		cadmiumsky	Rectangles (IOI19_rect)	C++17	100 / 100	1111 ms	202132 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 25e2 + 5;

#define lsb(x) (x & -x)
struct AIB {
   vector<int> v;
   vector<pii> st;
   void init(int n) {
      v.assign(n + 3, 0);
      st.clear();
   }
   template<int reverser = 0> void upd(int p, int x) {
      if(!reverser) st.emplace_back(p, x);
      ++p;
      while(p < sz(v)) v[p] += x, p += lsb(p);
   }
   int query(int p) {
      ++p;
      int sum = 0;
      while(p > 0) sum += v[p], p -= lsb(p);
      return sum;
   }
   int gettime() { return sz(st); }
   void revert() {
      if(!sz(st)) return;
      auto [a, b] = st.back();
      upd<1>(a, -b);
      st.pop_back();
   }
   void revert(int btime) {
      while(gettime() > btime) revert();
   }
};
AIB aib;

struct RangeCounter {
   pii mat[nmax][nmax];
   void init(int n) { for(int i = 0; i < n; i++) for(int j = i; j < n; j++) mat[i][j].second = -100; }
   void addright(int l, int r, int R) {
      if(r - l <= 1) return;
      //cerr << "\n(******)\nadding " << l << ' ' << r << '\t' << R << "\n(******)\n";
      if(mat[l][r].second != R - 1) mat[l][r].first = R;
      mat[l][r].second = R;
   }
   int qleft(int l, int r) { return mat[l][r].first - 1; }
};

RangeCounter hori, verti;

long long count_rectangles(std::vector<std::vector<int>> mat) {
   ll rez = 0;
   int n = sz(mat), m = sz(mat[0]);
   if(n < 3 || m < 3) return 0ll;
   hori.init(m + 1);
   verti.init(n + 1);
   
   aib.init(max(n, m) + 2);
   
   vector<vector<int>> colst(m, vector<int>());
   
   auto addcolcell = [&](vector<int>& leftcol, int i, int j) {
      //cerr << "Pentru verticale::\n";
      int lst = -12918;
      while(1) {
         if(colst[j].empty()) break;
         if(lst != mat[i][j]) {
            if(colst[j].back() < i - 1) leftcol.emplace_back(colst[j].back());
            verti.addright(colst[j].back(), i, j);
         }
         if(!(mat[colst[j].back()][j] <= mat[i][j])) break;
         lst = mat[colst[j].back()][j];
         colst[j].pop_back(); 
      }
      colst[j].emplace_back(i);
   };
   vector<int> sdfiasfifas_tmp;
   for(int i = 0; i < 2; i++)
      for(int j = 0; j < m; j++)
         addcolcell(sdfiasfifas_tmp, i, j);
   
   for(int i = 1; i < n - 1; i++) {
      vector<int> rowst;
      for(int j = 0; j < m; j++) {
         vector<int> leftcol, leftrow; // left pe row sau pe col
         
         {
            int lst = -129423;
            while(1) {
               if(rowst.empty()) break;
               if(lst != mat[i][j]) {
                  if(rowst.back() < j - 1) leftrow.emplace_back(rowst.back());
                  hori.addright(rowst.back(), j, i);
               }
               if(!(mat[i][rowst.back()] <= mat[i][j])) break;
               lst = mat[i][rowst.back()];
               rowst.pop_back(); 
            }
            rowst.emplace_back(j);
         }
         
         if(j >= 2) {
            addcolcell(leftcol, i + 1, j - 1);
            sort(all(leftrow), [&](int a, int b) { return hori.qleft(a, j) > hori.qleft(b, j); });
            
            int p = 0;
            aib.revert(0);
            for(auto x : leftrow) {
               while(p < sz(leftcol) && hori.qleft(x, j) <= leftcol[p])
                  aib.upd(verti.qleft(leftcol[p], i + 1), 1), ++p;
               rez += aib.query(x);
            }
         }
      
      }
   }
   
   return rez;
}


/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

• 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