oj.uz

Submission #844765

# Submission time Handle Problem Language Result Execution time Memory
844765 2023-09-05T21:03:08 Z garyye Rectangles (IOI19_rect) C++17
0 / 100
 334 ms 273812 KB 
#include "rect.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
typedef pair<int, int> i2;
typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;

long long count_rectangles(vvi A) {
  int n = SZ(A), m = SZ(A[0]);
  vvvi C(n, vvi(m));

  auto fun = [](vector<int> a) {
    vector<i2> ans;
    int s = SZ(a);
    vector<int> p(s), l(s, -1), r(s, -1);
    for (int i = 0; i < s; ++i) p[i] = i;
    sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });
    for (int i : p) {
      i2 x = {i, i};
      if (i > 0 && l[i - 1] != -1) x.fi = l[i - 1];
      if (i + 1 < s && r[i + 1] != -1) x.se = r[i + 1];

      if (x.fi > 0 && x.se + 1 < s && min(a[x.fi - 1], a[x.se + 1]) > a[i]) {
        ans.push_back(x);
      }
      r[x.fi] = x.se;
      l[x.se] = x.fi;
    }

    return ans;
  };

  for (int j = 0; j < m; ++j) {
    vector<int> col(n);
    for (int i = 0; i < n; ++i) col[i] = A[i][j];
    auto pp = fun(col);

    for (auto& [i1, i2] : pp) {
      C[i2][j].push_back(i1);
    }
  }

  ll ans = 0;
  vvi L(n, vi(m, -2));
  vvi R(n, vi(m, -2));
  for (int i = 0; i < n; ++i) {
    vector<int> p(m), l(m, -1), r(m, -1);
    for (int j = 0; j < m; ++j) p[j] = j;
    sort(p.begin(), p.end(), [&](int l, int r) -> bool { return A[i][l] < A[i][r]; });

    vector<set<int>> S(m);
    for (int j : p) {
      i2 x = {j, j};

      set<int> cur(ALL(C[i][j]));
      set<int> del;

      auto inspect = [&](set<int>& s) {
        for (int c : cur)
          if (!s.count(c))
            del.insert(c);
      };

      if (j > 0 && l[j - 1] != -1) {
        x.fi = l[j - 1];
        inspect(S[x.fi]);
      }
      if (j + 1 < m && r[j + 1] != -1) {
        x.se = r[j + 1];
        inspect(S[l[x.se]]);
      }

      for (int x : del) cur.erase(x);

      if (x.fi > 0 && x.se + 1 < m && min(A[i][x.fi - 1], A[i][x.se + 1]) > A[i][j]) {
        if (i - R[x.fi][x.se] > 1) {
          L[x.fi][x.se] = i;
        }
        R[x.fi][x.se] = i;
        for (int i1 : cur) {
          if (i1 >= L[x.fi][x.se]) {
            ans++;
          }
        }
      }
      r[x.fi] = x.se;
      l[x.se] = x.fi;
      S[x.fi] = cur;
    }
  }
  return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1372 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 0 ms 348 KB Output is correct
2 Runtime error 334 ms 273812 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 1 ms 348 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -