oj.uz

Submission #651564

# Submission time Handle Problem Language Result Execution time Memory
651564 2022-10-19T10:50:52 Z alvinpiter trapezoid (balkan11_trapezoid) C++17
100 / 100
 289 ms 21536 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 this) 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;
    }
  }

  // cout << "\ndp, numWays:\n";
  // for (int i = 1; i <= n; i++) {
  //   cout << i << ": " << dp[i] << " " << numWays[i] << endl;
  // }

  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 7 ms 14804 KB Output is correct
3 Correct 8 ms 14784 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 13 ms 14912 KB Output is correct
6 Correct 14 ms 14932 KB Output is correct
7 Correct 15 ms 15060 KB Output is correct
8 Correct 19 ms 15236 KB Output is correct
9 Correct 30 ms 15548 KB Output is correct
10 Correct 52 ms 16200 KB Output is correct
11 Correct 74 ms 16536 KB Output is correct
12 Correct 136 ms 18192 KB Output is correct
13 Correct 163 ms 18784 KB Output is correct
14 Correct 198 ms 19728 KB Output is correct
15 Correct 208 ms 19760 KB Output is correct
16 Correct 240 ms 20152 KB Output is correct
17 Correct 221 ms 20564 KB Output is correct
18 Correct 212 ms 20800 KB Output is correct
19 Correct 257 ms 21096 KB Output is correct
20 Correct 289 ms 21536 KB Output is correct