oj.uz

Submission #91453

# Submission time Handle Problem Language Result Execution time Memory
91453 2018-12-27T14:24:04 Z Mohammad_Yasser trapezoid (balkan11_trapezoid) C++14
5 / 100
 199 ms 40208 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;
  }
  if (curr >= N) {
    exit(0);
  }
}

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

    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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Runtime error 20 ms 16884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 21 ms 17192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 22 ms 17476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 20 ms 17624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 21 ms 17880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 22 ms 18136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 26 ms 18544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 37 ms 19664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 47 ms 21744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 56 ms 22940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 94 ms 28504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 133 ms 30768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 160 ms 32760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 165 ms 34296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 178 ms 35556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 176 ms 36352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 172 ms 37092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 187 ms 38484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 199 ms 40208 KB Execution killed with signal 11 (could be triggered by violating memory limits)