Submission #908615

#	Time	Username	Problem	Language	Result	Execution time	Memory
908615		duckindog	trapezoid (balkan11_trapezoid)	C++14	0 / 100	122 ms	39504 KiB

trapezoid

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

using namespace std;

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;
int f[4 * N];
void update(int s, int l, int r, int 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);
  f[s] = max(f[s * 2], f[s * 2 + 1]);

}
int query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return 0;
  if (u <= l && r <= v) return f[s];
  int mid = l + r >> 1;
  return max(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}

int 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};
  }
  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);
  }

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

    for (auto x : remind[i]) {
      int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      dp[x] = query(1, 1, 1e6, 1, c) + 1;
    }
    update(1, 1, 1e6, dp[i], r[i].d);

  }
  cout << *max_element(dp + 1, dp + n + 1);


}

Compilation message (stderr)

trapezoid.cpp: In function 'void update(int, int, int, int, int)':
trapezoid.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
trapezoid.cpp: In function 'int query(int, int, int, int, int)':
trapezoid.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = l + r >> 1;
      |             ~~^~~
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:61:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |       int mid = lt + rt >> 1;
      |                 ~~~^~~~
trapezoid.cpp:58:21: warning: unused variable 'b' [-Wunused-variable]
   58 |     int a = r[i].a, b = r[i].b;
      |                     ^
trapezoid.cpp:71:11: warning: unused variable 'a' [-Wunused-variable]
   71 |       int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      |           ^
trapezoid.cpp:71:23: warning: unused variable 'b' [-Wunused-variable]
   71 |       int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      |                       ^
trapezoid.cpp:71:47: warning: unused variable 'd' [-Wunused-variable]
   71 |       int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      |                                               ^
trapezoid.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100