oj.uz

Submission #204406

# Submission time Handle Problem Language Result Execution time Memory
204406 2020-02-25T16:40:08 Z ADJA Rectangles (IOI19_rect) C++14
0 / 100
 54 ms 632 KB 
#include "rect.h"
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
 
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
 
using namespace std;

const int MAXN = 2500;

int n, m;
int a[MAXN][MAXN];
int ok[MAXN][MAXN];
int mxc[MAXN];

int one[MAXN][MAXN], zero[MAXN][MAXN];

long long solveSix() {
  cerr << "here " << endl;

  for (int j = m - 1; j >= 0; j--) {
    for (int i = 0; i < n; i++) {
      if (a[i][j] == 0) {
        one[i][j] = 0;
        zero[i][j] = 1 + zero[i][j + 1];
      } else {
        zero[i][j] = 0;
        one[i][j] = 1 + one[i][j + 1];
      }
    }
  }

  cerr << "here2 " << endl;

  long long ans = 0;
  for (int j = 0; j + 1 < m; j++) {
    int prevOne = -1, mnZero = 123123, mxZero = -1;
    for (int i = 0; i < n; i++) {
      if (one[i][j + 1] == 0) {
        mxZero = max(mxZero, zero[i][j + 1]);
        mnZero = min(mnZero, zero[i][j + 1]);
      } else {
        int curOne = one[i][j + 1];
        if (prevOne != -1 && mxZero != -1 && mxZero == mnZero) {
          int zeroLen = mnZero;
          if (j + zeroLen + 1 < m && prevOne >= zeroLen && curOne >= zeroLen) {
            ans++;
          }
        }
        prevOne = curOne;
        mnZero = 123123, mxZero = -1;
      }
    }
  }

  return ans;
}

long long count_rectangles(std::vector<std::vector<int> > A) {
  n = sz(A); m = sz(A[0]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      a[i][j] = A[i][j];
    }
  }

  bool isSix = true;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] > 1) {
        isSix = false;
      }
    }
  }
  if (isSix) {
    cerr << "6" << endl;
    return solveSix();
  }

  long long ans = 0;

  for (int col = 0; col + 1 < m; col++) {
    for (int i = 0; i < n; i++) {
      for (int j = col; j < m; j++) {
        ok[i][j] = 0;
      }
    }
    for (int i = 0; i < n; i++) {
      int mx = -1;
      for (int j = col + 1; j < m; j++) {
        if (a[i][col] > mx && a[i][j] > mx) {
          ok[i][j] = 1;
        }
        if (a[i][j] > mx) {
          mx = a[i][j];
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = col + 1; j < m; j++) {
        if (ok[i][j]) {
          ok[i][j] = 1 + ok[i - 1][j];
        }
      }
    }

    for (int row = 0; row + 1 < n; row++) {
      for (int j = col + 1; j < m; j++) {
        mxc[j] = -1;
      }
      for (int row2 = row + 1; row2 < n; row2++) {
        bool good = true;
        for (int col2 = col + 1; col2 + 1 < m; col2++) {
          if (!(a[row][col2] > mxc[col2] && a[row2][col2] > mxc[col2])) {
            good = false;
          }
          if (good && row2 - 1 > row && ok[row2 - 1][col2 + 1] >= row2 - row - 1) {
            ans++;
          }
          if (a[row2][col2] > mxc[col2]) {
            mxc[col2] = a[row2][col2];
          }
        }
      }
    }
  }

  return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Incorrect 5 ms 632 KB secret mismatch
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Incorrect 5 ms 632 KB secret mismatch
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Incorrect 5 ms 632 KB secret mismatch
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Incorrect 5 ms 632 KB secret mismatch
6 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 504 KB Output is correct
2 Correct 39 ms 504 KB Output is correct
3 Incorrect 5 ms 504 KB secret mismatch
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Incorrect 5 ms 632 KB secret mismatch
6 Halted 0 ms 0 KB -