제출 #255510

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
255510	2020-08-01 06:51:38	rama_pang	Boat (APIO16_boat)	C++14	100 / 100	427 ms	4512 KiB

boat

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int N;
  cin >> N;
  vector<int> X = {0};
  vector<int> A(N + 1), B(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i] >> B[i];
    X.emplace_back(A[i]);
    X.emplace_back(B[i] + 1);
  }
  sort(begin(X), end(X));
  X.erase(unique(begin(X), end(X)), end(X));
  for (int i = 1; i <= N; i++) {
    A[i] = lower_bound(begin(X), end(X), A[i]) - begin(X);
    B[i] = upper_bound(begin(X), end(X), B[i]) - begin(X);
  }
  const int MOD = 1e9 + 7;
  vector<int> inv(N + 1);
  inv[0] = 0, inv[1] = 1;
  for (int i = 2; i <= N; i++) {
    inv[i] = (MOD - 1ll * (MOD / i) * inv[MOD % i] % MOD) % MOD;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42