Submission #585170

#	Time	Username	Problem	Language	Result	Execution time	Memory
585170		Pety	trapezoid (balkan11_trapezoid)	C++14	24 / 100	55 ms	8776 KiB

trapezoid

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

const int N = 30013;

struct Node {
  int best, count;
  Node operator + (const Node &other) {
    if (best == other.best)
      return {best, (other.count + count) % MOD};
    else if (best > other.best)
      return *this;
    else
      return other;
  }
} aint[4 * N], ans;

void update (int nod, int st, int dr, int poz, Node val) {
  if (st == dr) {
    aint[nod] = val;
    return;
  }
  int mij = (st + dr) / 2;
  if (poz <= mij)
    update(2 * nod, st, mij, poz, val);
  else
    update(2 * nod + 1, mij + 1, dr, poz, val);
  aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) {
    ans = ans + aint[nod];
    return;
  }
  int mij = (st + dr) / 2;
  if (a <= mij)
    query(2 * nod, st, mij, a, b);
  if (b > mij)
    query(2 * nod + 1, mij + 1, dr, a, b);
}

struct event {
  int type, time, x, ind;
  bool operator < (const event other) {
    return time < other.time;
  }
} v[N];

int a[N][4];

int n;
Node dp[N];

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  vector<int>idk;
  for (int i = 1; i <= n; i++) {
    for (auto j : {0, 1, 2, 3})
      cin >> a[i][j];
    idk.push_back(a[i][2]);
    idk.push_back(a[i][3]);
  }
  sort(idk.begin(), idk.end());
  for (int i = 1; i <= n; i++) {
    v[2 * i - 1] = {0, a[i][0], (int)(lower_bound(idk.begin(), idk.end(), a[i][2]) - idk.begin() + 1), i};
    v[2 * i] = {1, a[i][1], (int)(lower_bound(idk.begin(), idk.end(), a[i][3]) - idk.begin() + 1), i};
  }
  sort(v + 1, v + 2 * n + 1);
  for (int i = 1; i <= 2 * n; i++) {
    if (v[i].type == 1) {
      update(1, 1, 2 * n, v[i].x, dp[v[i].ind]);
    }
     else {
      ans = {0, 0};
       query(1, 1, 2 * n, 1, v[i].x);
       if (!ans.best) ans.count = 1;
       dp[v[i].ind] = {ans.best + 1, ans.count};
     }
  }
  ans = dp[1];
  for (int i = 2; i <= n; i++)
    ans = ans + dp[i];
  cout << ans.best << " " << ans.count;
  return 0;
}

• Subtask 1: 24 / 100