oj.uz

Submission #204397

# Submission time Handle Problem Language Result Execution time Memory
204397 2020-02-25T16:16:03 Z ADJA Rectangles (IOI19_rect) C++14
10 / 100
 5000 ms 52600 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];

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];
    }
  }

  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 = 0;
      for (int j = col + 1; j < m; j++) {
        if (a[i][col] > mx && a[i][j] > mx) {
          ok[i][j] = true;
        }
        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] = 0;
      }
      for (int row2 = row + 1; row2 < n; row2++) {
        for (int col2 = col + 1; col2 + 1 < m; col2++) {
          if (!(a[row][col2] > mxc[col2] && a[row2][col2] > mxc[col2])) {
            break;
          }
          if (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 6 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Incorrect 5 ms 504 KB Output isn't correct
7 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 6 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Incorrect 5 ms 504 KB Output isn't correct
7 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 6 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Incorrect 5 ms 504 KB Output isn't correct
7 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 6 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Incorrect 5 ms 504 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 504 KB Output is correct
2 Correct 36 ms 504 KB Output is correct
3 Correct 33 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 41 ms 504 KB Output is correct
6 Correct 43 ms 504 KB Output is correct
7 Correct 42 ms 504 KB Output is correct
8 Correct 40 ms 504 KB Output is correct
9 Correct 47 ms 504 KB Output is correct
10 Correct 13 ms 376 KB Output is correct
11 Correct 28 ms 504 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 5049 ms 52600 KB Time limit exceeded
3 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 6 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Incorrect 5 ms 504 KB Output isn't correct
7 Halted 0 ms 0 KB -