oj.uz

Submission #872978

# Submission time Handle Problem Language Result Execution time Memory
872978 2023-11-14T08:20:05 Z nguyentunglam Rectangles (IOI19_rect) C++17
49 / 100
 1314 ms 104636 KB 
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 710;

int a[N][N], L[N], R[N];

bitset<N> row[N][N], col[N][N];

long long count_rectangles (vector<vector<int> > _a) {
  int n = _a.size(), m = _a[0].size();

  for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = _a[i][j];

  for(int i = 1; i < n - 1; i++) {
    stack<int> st;
    for(int j = 0; j < m; j++) {
      while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
      L[j] = st.empty() ? 0 : st.top() + 1;
      st.push(j);
    }
    while (!st.empty()) st.pop();
    for(int j = m - 1; j >= 0; j--) {
      while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
      R[j] = st.empty() ? m : st.top() - 1;
      // cout << R[j] << " " << << endl;
      // if (j == 0) cout << st.top() << endl;
      st.push(j);
      // cout << st.top() << endl;
    }
    for(int j = 0; j < m; j++) row[L[j]][R[j]][i] = 1;
    // for(int j = m - 1; j >)
    // for(int j = 0; j < m; j++) cout << a[i][j] << " ";
    // for(int j = 0; j < m; j++) cout << L[j] << " " << R[j] << " " << i << endl;
    cout << endl;
  }

  for(int j = 1; j < m - 1; j++) {
    stack<int> st;
    for(int i = 0; i < n; i++) {
      while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
      L[i] = st.empty() ? 0 : st.top() + 1;
      // if (j == 2) cout << st.size() << endl;
      st.push(i);
    } 
    while (!st.empty()) st.pop();
    for(int i = n - 1; i >= 0; i--) {
      while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
      R[i] = st.empty() ? n : st.top() - 1;
      st.push(i);
    }
    for(int i = 0; i < n; i++) col[L[i]][R[i]][j] = 1;
  }

  // cout << endl;

  int ans = 0;

  // cout << col[4][4][2] << endl;

  // cout << n - 2 << endl;

  for(int left = 1; left < m - 1; left++) {
    for(int up = 1; up < n - 1; up++) for(int down = up; down < n - 1; down++) if (col[up][down][left]) {
      // cout << up << " " << down << endl;
      for(int right = left; right < m - 1 && col[up][down][right]; right++) {
        bool ok = 1;
        for(int j = up; j <= down && ok; j++) ok &= row[left][right][j];
        if (ok) {
          ans++;
          // cout << up << " " << down << " " << left << " " << right << endl;
          // cout << left << " " << right << " " << up << " " << down << endl;
        }
      }
    }
  }

  // cout << ans;

  return ans;
}

// int32_t main() {
//   #define task ""

//   cin.tie(0) -> sync_with_stdio(0);

//   if (fopen("task.inp", "r")) {
//     freopen("task.inp", "r", stdin);
//     freopen("task.out", "w", stdout);
//   }

//   if (fopen(task".inp", "r")) {
//     freopen (task".inp", "r", stdin);
//     freopen (task".out", "w", stdout);
//   }

//   int n, m; cin >> n >> m;

//   vector<vector<int> > _tmp;

//   for(int i = 0; i < n; i++) {
//     vector<int> tmp;
//     for(int j = 0; j < m; j++) {
//       int x; cin >> x;
//       tmp.push_back(x);
//     }
//     _tmp.push_back(tmp);
//   }

//   count_rectangles(_tmp);
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 4696 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 4696 KB Output is correct
22 Correct 3 ms 16728 KB Output is correct
23 Correct 3 ms 16732 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 3 ms 16732 KB Output is correct
26 Correct 3 ms 16732 KB Output is correct
27 Correct 3 ms 16804 KB Output is correct
28 Correct 3 ms 16728 KB Output is correct
29 Correct 2 ms 14684 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 3 ms 16728 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 3 ms 16804 KB Output is correct
23 Correct 3 ms 16728 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 4696 KB Output is correct
30 Correct 20 ms 33616 KB Output is correct
31 Correct 20 ms 33628 KB Output is correct
32 Correct 22 ms 33900 KB Output is correct
33 Correct 11 ms 33624 KB Output is correct
34 Correct 12 ms 33624 KB Output is correct
35 Correct 13 ms 33884 KB Output is correct
36 Correct 13 ms 33884 KB Output is correct
37 Correct 13 ms 33880 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 3 ms 16728 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 3 ms 16804 KB Output is correct
23 Correct 3 ms 16728 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 20 ms 33616 KB Output is correct
26 Correct 20 ms 33628 KB Output is correct
27 Correct 22 ms 33900 KB Output is correct
28 Correct 11 ms 33624 KB Output is correct
29 Correct 12 ms 33624 KB Output is correct
30 Correct 13 ms 33884 KB Output is correct
31 Correct 13 ms 33884 KB Output is correct
32 Correct 13 ms 33880 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 8540 KB Output is correct
36 Correct 1 ms 6492 KB Output is correct
37 Correct 1 ms 4696 KB Output is correct
38 Correct 935 ms 104116 KB Output is correct
39 Correct 906 ms 104260 KB Output is correct
40 Correct 897 ms 104052 KB Output is correct
41 Correct 940 ms 104052 KB Output is correct
42 Correct 1257 ms 104056 KB Output is correct
43 Correct 1280 ms 104276 KB Output is correct
44 Correct 1314 ms 104368 KB Output is correct
45 Correct 1093 ms 101960 KB Output is correct
46 Correct 905 ms 101680 KB Output is correct
47 Correct 893 ms 102024 KB Output is correct
48 Correct 948 ms 102736 KB Output is correct
49 Correct 921 ms 104636 KB Output is correct
50 Correct 461 ms 78164 KB Output is correct
51 Correct 84 ms 80212 KB Output is correct
52 Correct 888 ms 103504 KB Output is correct
53 Correct 972 ms 104576 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4696 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Runtime error 53 ms 55892 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 3 ms 16728 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Correct 3 ms 16732 KB Output is correct
22 Correct 3 ms 16804 KB Output is correct
23 Correct 3 ms 16728 KB Output is correct
24 Correct 2 ms 14684 KB Output is correct
25 Correct 20 ms 33616 KB Output is correct
26 Correct 20 ms 33628 KB Output is correct
27 Correct 22 ms 33900 KB Output is correct
28 Correct 11 ms 33624 KB Output is correct
29 Correct 12 ms 33624 KB Output is correct
30 Correct 13 ms 33884 KB Output is correct
31 Correct 13 ms 33884 KB Output is correct
32 Correct 13 ms 33880 KB Output is correct
33 Correct 935 ms 104116 KB Output is correct
34 Correct 906 ms 104260 KB Output is correct
35 Correct 897 ms 104052 KB Output is correct
36 Correct 940 ms 104052 KB Output is correct
37 Correct 1257 ms 104056 KB Output is correct
38 Correct 1280 ms 104276 KB Output is correct
39 Correct 1314 ms 104368 KB Output is correct
40 Correct 1093 ms 101960 KB Output is correct
41 Correct 905 ms 101680 KB Output is correct
42 Correct 893 ms 102024 KB Output is correct
43 Correct 948 ms 102736 KB Output is correct
44 Correct 921 ms 104636 KB Output is correct
45 Correct 461 ms 78164 KB Output is correct
46 Correct 84 ms 80212 KB Output is correct
47 Correct 888 ms 103504 KB Output is correct
48 Correct 972 ms 104576 KB Output is correct
49 Runtime error 4 ms 4696 KB Execution killed with signal 11
50 Halted 0 ms 0 KB -