oj.uz

Submission #91455

# Submission time Handle Problem Language Result Execution time Memory
91455 2018-12-27T14:33:03 Z Mohammad_Yasser trapezoid (balkan11_trapezoid) C++14
100 / 100
 286 ms 20284 KB 
#include <bits/stdc++.h>
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
typedef long long Long;
typedef unsigned long long ULong;

constexpr int N = 2e5 + 5;
const int MOD = 30013;

struct Node {
  int start, end; // The node covers the range [start,end].

  int mx = 0;
  int no_ways = 0;

  void merge(int other_mx, int other_ways) {
    if (mx > other_mx) return;
    if (mx == other_mx) {
      no_ways = (no_ways + other_ways) % MOD;
      return;
    }
    mx = other_mx;
    no_ways = other_ways;
  }

  void merge(const Node& right) {
    end = right.end;
    merge(right.mx, right.no_ways);
  }

  static Node merge(const Node& a, const Node& b) {
    Node res = a;
    res.merge(b);
    return res;
  }

  bool inRange(int x) const {
    return start <= x && x <= end;
  }

  void print() const {

  }
};

struct SegmentTree {
  static const int kSize = 1 << int(log2(N) + 2);

  Node nodes[kSize];

  void build(int node_id, int left, int right) {
    Node& node = nodes[node_id];
    node.start = left, node.end = right;
    if (left == right) return;

    int mid = (left + right) / 2;
    build(node_id * 2, left, mid);
    build(node_id * 2 + 1, mid + 1, right);
  }

  void update(int node_id, int b, int mx, int ways) {
    auto& node = nodes[node_id];
    if (!node.inRange(b)) return;
    if (node.start == node.end) {
      node.merge(mx, ways);
      return;
    }
    update(node_id * 2, b, mx, ways);
    update(node_id * 2 + 1, b, mx, ways);
    node = Node::merge(nodes[node_id * 2], nodes[node_id * 2 + 1]);
  }

  Node query(int node_id, int r) {
    auto& node = nodes[node_id];
    if (r >= node.end) return node;

    Node a = query(node_id * 2, r);

    if (r <= a.end) return a;

    Node b = query(node_id * 2 + 1, r);

    Node res = Node::merge(a, b);
    return res;
  }

} tree;

map<int, int> comp;

struct Trapezoid {
  int a, b, c, d;
};

void buildComp() {
  int curr = 0;
  for (auto& p : comp) {
    p.second = ++curr;
  }
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  int n;
  cin >> n;
  vector<Trapezoid> traps(n);

  for (auto& trap : traps) {
    cin >> trap.a >> trap.b >> trap.c >> trap.d;
    comp[trap.a], comp[trap.b];
  }

  buildComp();

  sort(traps.begin(), traps.end(), [](const Trapezoid& a , const Trapezoid& b) {
    return a.c < b.c;
  });

  for (auto& trap : traps) {
    trap.a = comp[trap.a], trap.b = comp[trap.b];
  }

  tree.build(1, 1, N - 1);
  set<pair<int, tuple<int, int, int>>> updates;
  for (auto& trap : traps) {
    while (!updates.empty() && updates.begin()->first < trap.c) {
      auto update = *updates.begin();
      updates.erase(updates.begin());
      tree.update(1, get<0>(update.second), get<1>(update.second),
        get<2>(update.second));
    }

    if (trap.a == 1) {
      updates.emplace(trap.d, make_tuple(trap.b, 1, 1));
    } else {
      Node query = tree.query(1, trap.a - 1);
      updates.emplace(trap.d,
        make_tuple(trap.b, query.mx + 1, max(1, query.no_ways)));
    }
  }

  while (!updates.empty()) {
    auto update = *updates.begin();
    updates.erase(updates.begin());
    tree.update(1, get<0>(update.second), get<1>(update.second),
      get<2>(update.second));
  }

  cout << tree.nodes[1].mx << " " << tree.nodes[1].no_ways << endl;

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8568 KB Output is correct
2 Correct 9 ms 8568 KB Output is correct
3 Correct 10 ms 8848 KB Output is correct
4 Correct 10 ms 8848 KB Output is correct
5 Correct 13 ms 8932 KB Output is correct
6 Correct 13 ms 9228 KB Output is correct
7 Correct 14 ms 9276 KB Output is correct
8 Correct 17 ms 9424 KB Output is correct
9 Correct 29 ms 9956 KB Output is correct
10 Correct 41 ms 11232 KB Output is correct
11 Correct 52 ms 11616 KB Output is correct
12 Correct 111 ms 14560 KB Output is correct
13 Correct 146 ms 15676 KB Output is correct
14 Correct 178 ms 16620 KB Output is correct
15 Correct 205 ms 17388 KB Output is correct
16 Correct 238 ms 17996 KB Output is correct
17 Correct 228 ms 18616 KB Output is correct
18 Correct 208 ms 18868 KB Output is correct
19 Correct 219 ms 19424 KB Output is correct
20 Correct 286 ms 20284 KB Output is correct