oj.uz

답안 #585170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585170 2022-06-28T11:34:57 Z Pety 사다리꼴 (balkan11_trapezoid) C++14
24 / 100
 55 ms 8776 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 468 KB Partially correct
5 Partially correct 2 ms 520 KB Partially correct
6 Partially correct 3 ms 724 KB Partially correct
7 Partially correct 4 ms 856 KB Partially correct
8 Partially correct 5 ms 980 KB Partially correct
9 Partially correct 10 ms 1748 KB Partially correct
10 Runtime error 21 ms 5056 KB Execution killed with signal 11
11 Runtime error 23 ms 5200 KB Execution killed with signal 11
12 Runtime error 33 ms 6632 KB Execution killed with signal 11
13 Runtime error 35 ms 7008 KB Execution killed with signal 11
14 Runtime error 39 ms 7652 KB Execution killed with signal 11
15 Runtime error 44 ms 7676 KB Execution killed with signal 11
16 Runtime error 45 ms 7876 KB Execution killed with signal 11
17 Runtime error 47 ms 8224 KB Execution killed with signal 11
18 Runtime error 50 ms 8288 KB Execution killed with signal 11
19 Runtime error 49 ms 8576 KB Execution killed with signal 11
20 Runtime error 55 ms 8776 KB Execution killed with signal 11