oj.uz

Submission #651565

# Submission time Handle Problem Language Result Execution time Memory
651565 2022-10-19T10:52:47 Z alvinpiter trapezoid (balkan11_trapezoid) C++17
100 / 100
 273 ms 18756 KB 
/*
Let's sort the trapezoid by its top-left coordinate, in increasing order.

Define:
dp[i] = The size of max independent set of trapezoids that can be formed using the i-th trapezoid upto the last
trapezoid, and the i-th trapezoid is included in the set.

dp[i] = max(1 + dp[j]), where the j-th (j > i) trapezoid doesn't intersect with the i-th trapezoid.

Naive implementation will take O(N^2) time. The bottleneck of the solution is in finding the trapezoid
that doesn't intersect with the current trapezoid.

To speed up the solution, we need a data structure that can support the following queries:
* Get the value of dp[j] (and number of ways to achieve it) for all trapezoids whose lower-left corner is larger than
  a certain value.
* Insert the value of dp[j] for a trapezoid whose lower-left corner is a certain value.

We have to be careful when dealing with the above data structure. We only insert trapezoids whose top-left corner is larger
than the current trapezoid's top-right corner. This can be ensured by processing the top points of the trapezoids from the
right most one. Whenever we encounter a top-right corner, we query, and whenever we encounter a top-left corner, we insert.
*/

#include<bits/stdc++.h>
using namespace std;
#define MAXV 400001
#define MAXN 100000
#define MOD 30013

int n, t[MAXN + 3][4], topPointOwner[MAXV + 3], dp[MAXN + 3], numWays[MAXN + 3];
bool isTopLeftPoint[MAXV + 3];
vector<int> uniqueCoordinates;
pair<int, int> tree[4 * MAXV + 3];

pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
  if (a.first != b.first) {
    return a.first < b.first ? b : a;
  } else {
    return make_pair(a.first, (a.second + b.second)%MOD);
  }
}

void doUpdate(int node, int l, int r, int idx, int sz, int ways) {
  if (r < idx || l > idx) {
    return;
  }

  if (l == r) {
    tree[node] = {sz, ways};
    return;
  }

  int m = (l + r)/2;
  doUpdate(2 * node, l, m, idx, sz, ways);
  doUpdate(2 * node + 1, m + 1, r, idx, sz, ways);

  tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}

void update(int idx, int sz, int ways) {
  doUpdate(1, 1, MAXV, idx, sz, ways);
}

pair<int, int> doQuery(int node, int l, int r, int ql, int qr) {
  if (r < ql || l > qr) {
    return {0, 0};
  }

  if (l >= ql && r <= qr) {
    return tree[node];
  }

  int m = (l + r)/2;
  return combine(doQuery(2 * node, l, m, ql, qr), doQuery(2 * node + 1, m + 1, r, ql, qr));
}

pair<int, int> query(int idx) {
  return doQuery(1, 1, MAXV, idx, MAXV);
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> t[i][j];
      uniqueCoordinates.push_back(t[i][j]);
    }
  }

  sort(uniqueCoordinates.begin(), uniqueCoordinates.end());
  uniqueCoordinates.erase(unique(uniqueCoordinates.begin(), uniqueCoordinates.end()), uniqueCoordinates.end());

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 4; j++) {
      t[i][j] = (lower_bound(uniqueCoordinates.begin(), uniqueCoordinates.end(), t[i][j]) - uniqueCoordinates.begin()) + 1;
    }
  }

  memset(topPointOwner, -1, sizeof(topPointOwner));
  memset(isTopLeftPoint, false, sizeof(isTopLeftPoint));
  for (int i = 1; i <= n; i++) {
    topPointOwner[t[i][0]] = topPointOwner[t[i][1]] = i;
    isTopLeftPoint[t[i][0]] = true;
  }

  for (int c = 1; c <= 4 * MAXV; c++) {
    tree[c] = {0, 0};
  }
  update(MAXV, 0, 1);

  for (int c = MAXV - 1; c >= 1; c--) {
    if (topPointOwner[c] == -1) {
      continue;
    }

    int owner = topPointOwner[c];

    if (isTopLeftPoint[c]) {
      update(t[owner][2], dp[owner], numWays[owner]);
    } else {
      auto queryResult = query(t[owner][3] + 1);
      dp[owner] = 1 + queryResult.first;
      numWays[owner] = queryResult.second;
    }
  }

  pair<int, int> ans = {0, 0};
  for (int i = 1; i <= n; i++) {
    ans = combine(ans, {dp[i], numWays[i]});
  }

  cout << ans.first << " " << ans.second << endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14804 KB Output is correct
2 Correct 8 ms 14736 KB Output is correct
3 Correct 8 ms 14804 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 12 ms 14908 KB Output is correct
6 Correct 16 ms 14932 KB Output is correct
7 Correct 16 ms 14960 KB Output is correct
8 Correct 17 ms 15060 KB Output is correct
9 Correct 31 ms 15424 KB Output is correct
10 Correct 52 ms 15644 KB Output is correct
11 Correct 74 ms 15852 KB Output is correct
12 Correct 135 ms 16916 KB Output is correct
13 Correct 155 ms 17216 KB Output is correct
14 Correct 190 ms 17592 KB Output is correct
15 Correct 203 ms 17856 KB Output is correct
16 Correct 213 ms 18112 KB Output is correct
17 Correct 220 ms 18180 KB Output is correct
18 Correct 223 ms 18428 KB Output is correct
19 Correct 242 ms 18616 KB Output is correct
20 Correct 273 ms 18756 KB Output is correct