結果
問題 | No.871 かえるのうた |
ユーザー |
![]() |
提出日時 | 2019-08-30 21:53:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 1,378 bytes |
コンパイル時間 | 1,341 ms |
コンパイル使用メモリ | 170,396 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-30 10:46:36 |
合計ジャッジ時間 | 4,121 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;typedef pair<ll, P> P3;typedef pair<P, P> PP;constexpr ll MOD = ll(1e9 + 7);constexpr int IINF = INT_MAX;constexpr ll LLINF = LLONG_MAX;constexpr int MAX_N = int(1e5) + 5;constexpr double EPS = 1e-9;constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};#define REP(i, n) for (int i = 0; i < n; i++)#define REPR(i, n) for (int i = n; i >= 0; i--)#define SORT(v) sort((v).begin(), (v).end())#define SORTR(v) sort((v).rbegin(), (v).rend())#define ALL(v) (v).begin(), (v).end()int main() {ll n, k;cin >> n >> k;vector<ll> x(n+2), a(n+2);for(int i=0;i<n;i++){cin >> x[i+1];}for(int i=0;i<n;i++){cin >> a[i+1];}x[0] = -LLINF/3;x[n+1] = LLINF/3;ll l = k, r = k;ll lpos = x[l], rpos = x[r];bool update = true;while(update){update = false;for(; r<n+1; r++){rpos = max(rpos, x[r]+a[r]);lpos = min(lpos, x[r]-a[r]);if(x[r+1] > rpos) break;update = true;}for(; l>0; l--){rpos = max(rpos, x[l]+a[l]);lpos = min(lpos, x[l]-a[l]);if(x[l-1] < lpos) break;update = true;}}cout << r-l+1 << endl;return 0;}