Submission #908506

#	Time	Username	Problem	Language	Result	Execution time	Memory
908506		duckindog	trapezoid (balkan11_trapezoid)	C++14	28 / 100	36 ms	628 KiB

trapezoid

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10,
          M = 30013;
struct rec {
  int a = 0, b = 0, c = 0, d = 0;

  bool operator < (const rec& rhs) {
    return make_pair(min(a, c), min(b, d)) < make_pair(min(rhs.a, rhs.c), min(rhs.b, rhs.d));
  }
} r[N];
int n;
int d[N], f[N];
bool crossed(rec x, rec y) {
  if (min(x.a, x.c) > min(y.a, y.c)) swap(x, y);
  return (x.b >= y.a || x.d >= y.c);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    r[i] = {a, b, c, d};
  }
  sort(r + 1, r + n + 1);

  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (!crossed(r[i], r[j])) {
        if (d[i] == d[j] + 1) f[i] = (f[i] + f[j]) % M;
        else f[i] = f[j];
        d[i] = max(d[i], d[j] + 1);
      }
    }
  }

  int ma = *max_element(d + 1, d + n + 1);
  int cnt = 0;
  for (int i = 1; i <= n; ++i) if (d[i] == ma) cnt = (cnt + f[i]) % M;
  cout << ma << ' ' << cnt << '\n';

}

Compilation message (stderr)

trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 100