Submission #908677

#	Time	Username	Problem	Language	Result	Execution time	Memory
908677		duckindog	trapezoid (balkan11_trapezoid)	C++14	100 / 100	216 ms	55968 KiB

trapezoid

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

using namespace std;

#define int long long

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

  bool operator < (const rec& rhs) {
    return make_pair(b, d) < make_pair(rhs.b, rhs.b);
  }
} r[N];
int 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);
}
vector<int> remind[N];
vector<int> rrh;
using pii = pair<int, int>;
pair<int, int> f[4 * N];
void update(int s, int l, int r, pii x, int y) {
  if (y < l || y > r) return;
  if (l == r) {
    f[s] = max(f[s], x);
    return;
  }
  int mid = l + r >> 1;
  update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
  int ma = max(f[s * 2].first, f[s * 2 + 1].first);
  f[s].first = ma;
  f[s].second = (f[s * 2].second * (f[s * 2].first == ma) + f[s * 2 + 1].second * (f[s * 2 + 1].first == ma)) % M;

}
pii query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return {0, 0};
  if (u <= l && r <= v) return f[s];
  int mid = l + r >> 1;
  auto lt = query(s * 2, l, mid, u, v), rt = query(s * 2 + 1, mid + 1, r, u, v);
  int ma = max(lt.first, rt.first);
  return {ma, (lt.second * (lt.first == ma) + rt.second * (rt.first == ma)) % M};

}

pii dp[N];

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};
    rrh.push_back(c), rrh.push_back(d);
  }
  sort(rrh.begin(), rrh.end());
  map<int, int> rvs;
  for (int i = 0; i < rrh.size(); ++i) rvs[rrh[i]] = i + 1;
  int sz = rrh.size();

  sort(r + 1, r + n + 1);

  for (int i = 1; i <= n; ++i) {
    int a = r[i].a, b = r[i].b;
    int lt = 0, rt = i - 1, it = 0;
    while (lt <= rt) {
      int mid = lt + rt >> 1;
      if (r[mid].b <= a) lt = (it = mid) + 1;
      else rt = mid - 1;
    }
    remind[it].push_back(i);

  }

  dp[0] = {0, 1};

  for (int i = 0; i <= n; ++i) {

    update(1, 0, sz, dp[i], rvs[r[i].d]);
    for (auto x : remind[i]) {
      int c = r[x].c, d = r[x].d;
      dp[x] = query(1, 0, sz, 0, rvs[c]);
      dp[x].first += 1;
    }

  }
  auto answer = query(1, 0, sz, 0, sz);
  cout << answer.first << ' ' << answer.second;

}

Compilation message (stderr)

trapezoid.cpp: In function 'void update(long long int, long long int, long long int, pii, long long int)':
trapezoid.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid = l + r >> 1;
      |             ~~^~~
trapezoid.cpp: In function 'pii query(long long int, long long int, long long int, long long int, long long int)':
trapezoid.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid = l + r >> 1;
      |             ~~^~~
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:67:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < rrh.size(); ++i) rvs[rrh[i]] = i + 1;
      |                   ~~^~~~~~~~~~~~
trapezoid.cpp:76:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |       int mid = lt + rt >> 1;
      |                 ~~~^~~~
trapezoid.cpp:73:21: warning: unused variable 'b' [-Wunused-variable]
   73 |     int a = r[i].a, b = r[i].b;
      |                     ^
trapezoid.cpp:90:23: warning: unused variable 'd' [-Wunused-variable]
   90 |       int c = r[x].c, d = r[x].d;
      |                       ^
trapezoid.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100