結果
問題 | No.871 かえるのうた |
ユーザー |
![]() |
提出日時 | 2019-08-30 22:52:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,870 ms / 2,000 ms |
コード長 | 2,185 bytes |
コンパイル時間 | 1,582 ms |
コンパイル使用メモリ | 170,356 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-30 10:49:06 |
合計ジャッジ時間 | 6,570 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)#define rep(i, n) REP(i, 0, n)#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()#define pb push_back#define mp make_pairtypedef long long ll;const ll INF = 1LL << 60;const ll mod = 1e9 + 7;template <class T>bool chmax(T &a, const T &b){if (a < b){a = b;return 1;}return 0;}template <class T>bool chmin(T &a, const T &b){if (b < a){a = b;return 1;}return 0;}ll modpow(ll a, ll p){if (p == 0)return 1;if (!(p % 2)){ll halfP = p / 2;ll half = modpow(a, halfP);return half * half % mod;}else{return a * modpow(a, p - 1) % mod;}}ll comb(int a, int b){if (b > a - b)return comb(a, a - b);ll ansMul = 1;ll ansDiv = 1;for (int i = 0; i < b; i++){ansMul *= a - i;ansDiv *= i + 1;ansMul %= mod;ansDiv %= mod;}ll ans = ansMul * modpow(ansDiv, mod - 2) % mod;return ans;}/*int num = 200010;vector<ll> fact(num), ifact(num);fact[0] = 1;fact[1] = 1;for (int i = 2; i < num; i++) {fact[i] = fact[i-1] * i;fact[i] %= mod;}for (int i = 0; i < num; i++) {ifact[i] = modpow(ifact[i], mod-2);ifact[i] %= mod;}*/int main() {int N, K; cin >> N >> K;vector<ll> X(N), A(N);rep(i, N) cin >> X[i];rep(i, N) cin >> A[i];if (X[0] < 0) {ll v = -X[0];rep(i, N) {X[i] += v;}}K--;ll l = X[K] - A[K];ll r = X[K] + A[K];int res = 0;while (true) {int ld = lower_bound(all(X), l) - X.begin();int rd = lower_bound(all(X), r) - X.begin();if (r != X[rd]) rd--;for (int i = ld; i <= rd; i++) {l = min(l, X[i] - A[i]);r = max(r, X[i] + A[i]);}int tmp = res;res = rd - ld + 1;if (res == tmp) break;}cout << res << endl;return 0;}