結果

問題 No.871 かえるのうた
ユーザー ateate
提出日時 2019-11-20 23:10:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 3,467 bytes
コンパイル時間 2,550 ms
コンパイル使用メモリ 220,996 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-07 16:35:29
合計ジャッジ時間 6,115 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 14 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 AC 111 ms
5,376 KB
testcase_15 AC 108 ms
5,376 KB
testcase_16 AC 116 ms
5,376 KB
testcase_17 AC 93 ms
5,376 KB
testcase_18 AC 16 ms
5,376 KB
testcase_19 AC 109 ms
5,376 KB
testcase_20 AC 10 ms
5,376 KB
testcase_21 AC 42 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 6 ms
5,376 KB
testcase_27 AC 9 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 33 ms
5,376 KB
testcase_30 AC 59 ms
5,376 KB
testcase_31 AC 4 ms
5,376 KB
testcase_32 AC 48 ms
5,376 KB
testcase_33 AC 79 ms
5,376 KB
testcase_34 AC 19 ms
5,376 KB
testcase_35 AC 51 ms
5,376 KB
testcase_36 AC 68 ms
5,376 KB
testcase_37 AC 42 ms
5,376 KB
testcase_38 AC 93 ms
5,376 KB
testcase_39 AC 86 ms
5,376 KB
testcase_40 AC 28 ms
5,376 KB
testcase_41 AC 1 ms
5,376 KB
testcase_42 AC 27 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 2 ms
5,376 KB
testcase_46 AC 1 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main(){solve2();}
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
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(a>b){a=b;return 1;}return 0;}
void dump(){cout<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cout<<h<<", ";dump(forward<Ts>(t)...);}
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
void solve1();
void solve2();
main(){solve2();}

void solve2(){
  ll n,k;
  cin>>n>>k;
  k--;
  vector<ll> x(n),a(n);
  cin>>x>>a;

  bool updated = true;
  ll lidx,ridx,left,right;
  lidx = ridx = k;
  left = x[k]-a[k];
  right = x[k]+a[k];
  while(updated){
    updated = false;
    while(lidx>0&&left<=x[lidx-1]){
      updated = true;
      lidx--;
      chmin(left,x[lidx]-a[lidx]);
      chmax(right,x[lidx]+a[lidx]);
    }
    while(ridx+1<n&&x[ridx+1]<=right){
      updated = true;
      ridx++;
      chmax(right,x[ridx]+a[ridx]);
      chmin(left,x[ridx]-a[ridx]);
    }
  }
  cout<<(ridx-lidx+1)<<endl;

}

template<class T>
class segtree {
private:
  ll n=1;
  T unit;
  std::vector<T> dat;
  std::function<T(T,T)> func;
public:
  segtree(){}
  segtree(std::vector<T>& a,T v,std::function<T(T,T)> f){
    build(a,v,f);
  }
  void build(std::vector<T>& a,T v,std::function<T(T,T)> f){
    ll sz=a.size();
    unit=v;
    func=f;
    while(n<sz)n<<=1LL;
    dat.resize(2*n-1,unit);
    for(int i=0;i<sz;++i)dat[i+n-1]=a[i];
    for(int i=n-2;i>=0;--i){
      dat[i]=func(dat[i*2+1],dat[i*2+2]);
    }
  }
  void update(ll idx,T val){
    idx+=n-1;
    dat[idx]=val;
    while(idx){
      idx--;idx>>=1LL;
      dat[idx]=func(dat[idx*2+1],dat[idx*2+2]);
    }
  }
  T query(ll a,ll b,ll k=0,ll l=0,ll r=-1){
    if(r<0)r=n;
    if( b<=l || r<=a )return unit;
    if( a<=l && r<=b )return dat[k];
    else{
      auto left=query(a,b,2*k+1,l,(l+r)/2);
      auto right=query(a,b,2*k+2,(l+r)/2,r);
      return func(left,right);
    }
  }
};


void solve1(){

  ll n,k;
  cin>>n>>k;
  k--;
  vector<ll> x(n),a(n);
  cin>>x>>a;

  vector<pll> left(n),right(n);
  rep(i,n){
    left[i].first=x[i]+a[i];
    right[i].first=x[i]-a[i];
    left[i].second=right[i].second=i;
  }

  segtree<pll> leftmax(left,pll(-INF,-INF),[](auto a,auto b){return max(a,b);});
  segtree<pll> rightmin(right,pll(INF,INF),[](auto a,auto b){return min(a,b);});

  ll low=k,high=k;
  vector<bool> seen(n,false);
  queue<ll> que;
  que.emplace(k);
  while(!que.empty()){
    ll i = que.front();
    que.pop();
    if(seen[i])continue;
    seen[i]=true;
    auto litr = upper_bound(x.begin(),x.end(),left[i].first);
    litr--;
    ll lidx = litr-x.begin();
    chmax(high,lidx);
    pll lm = leftmax.query(i,lidx+1);
    que.emplace(lm.second);
    auto ritr = lower_bound(x.begin(),x.end(),right[i].first);
    ll ridx = ritr-x.begin();
    chmin(low,ridx);
    pll rm = rightmin.query(ridx,i+1);
    que.emplace(rm.second);
  }

  cout<<(high-low+1)<<endl;

}
0