結果
問題 |
No.1055 牛歩
|
ユーザー |
![]() |
提出日時 | 2020-05-15 22:32:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 557 ms / 1,000 ms |
コード長 | 8,859 bytes |
コンパイル時間 | 5,630 ms |
コンパイル使用メモリ | 216,944 KB |
最終ジャッジ日時 | 2025-01-10 11:49:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } #define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } //merge で片方が inactive のときはもう片方をそのまま返す, //といったときに,lazy の情報までコピーして渡さないようにする //get の最後の引数は単位元と口では言いつつ・・・? //たとえば min で最後の引数を 0 にしても 1 とかが返ってくることはある(一敗) //VERIFY: yosupo //KUPC2017I //HDU 5306 Gorgeous Sequence //findmin/max CF458E template<class N> struct segbeats{ vc<N> x; int s; segbeats(){} template<class T> segbeats(const vc<T>& a){ int n=a.size(); s=1; while(s<n)s*=2; x.resize(s*2); rep(i,n) x[s+i]=N(a[i]); gnr(i,1,s) upd(i); } void push(int i){ x[i].push(x[i*2],x[i*2+1]); } void upd(int i){ x[i]=N::merge(x[i*2],x[i*2+1]); } template<class F,class... Args> void chr(int l,int r,int i,int b,int e,F f,Args&&... args){ if(e<=l||r<=b) return; if(b<=l&&r<=e&&(x[i].*f)(forward<Args>(args)...)) return; push(i); int m=(l+r)/2; chr(l,m,i*2,b,e,f,forward<Args>(args)...); chr(m,r,i*2+1,b,e,f,forward<Args>(args)...); upd(i); } template<class F,class... Args> void ch(int b,int e,F f,Args&&... args){ assert(b<=e); chr(0,s,1,b,e,f,forward<Args>(args)...); } //use decltype((declval<N>().*F())()) for old-fashioned judges template<class F,class G,class H> auto getr(int l,int r,int i,int b,int e,F f,G g,H h){ if(e<=l||r<=b) return h; if(b<=l&&r<=e) return (x[i].*f)(); push(i); int m=(l+r)/2; return g(getr(l,m,i*2,b,e,f,g,h),getr(m,r,i*2+1,b,e,f,g,h)); } template<class F,class G,class H> auto get(int b,int e,F f,G g,H h){ assert(b<=e); return getr(0,s,1,b,e,f,g,h); } //return minimum index template<class F,class...Args> pair<int,N> findminr(int i,int l,int r,int b,int e,F f,Args&&...args){ if(e<=l||r<=b)return {e,N()}; if(b<=l&&r<=e){ if(!(x[i].*f)(forward<Args>(args)...))return {e,N()}; if(r-l==1)return {l,x[i]}; } push(i); int m=(l+r)/2; auto a=findminr(i*2,l,m,b,e,f,forward<Args>(args)...); if(a.a<e)return a; return findminr(i*2+1,m,r,b,e,f,forward<Args>(args)...); } template<class F,class...Args> pair<int,N> findmin(int b,int e,F f,Args&&...args){ assert(b<=e); return findminr(1,0,s,b,e,f,forward<Args>(args)...); } //return maximum index template<class F,class...Args> pair<int,N> findmaxr(int i,int l,int r,int b,int e,F f,Args&&...args){ if(e<=l||r<=b)return {b-1,N()}; if(b<=l&&r<=e){ if(!(x[i].*f)(forward<Args>(args)...))return {b-1,N()}; if(r-l==1)return {l,x[i]}; } push(i); int m=(l+r)/2; auto a=findmaxr(i*2+1,m,r,b,e,f,forward<Args>(args)...); if(a.a>=b)return a; return findmaxr(i*2,l,m,b,e,f,forward<Args>(args)...); } template<class F,class...Args> pair<int,N> findmax(int b,int e,F f,Args&&...args){ assert(b<=e); return findmaxr(1,0,s,b,e,f,forward<Args>(args)...); } void enumerater(int l,int r,int i,int b,int e,vc<N>&dst){ if(e<=l||r<=b) return; if(l+1==r){ dst.pb(x[i]); return; } push(i); int m=(l+r)/2; enumerater(l,m,i*2,b,e,dst); enumerater(m,r,i*2+1,b,e,dst); } void enumerate(int b,int e,vc<N>&dst){ assert(b<=e); return enumerater(0,s,1,b,e,dst); } void prepare(int i){ if(i/=2){ prepare(i); push(i); } } //point_update と lazy を組み合わせたらどうなるかは,わからない・・・ void point_update(int i,N w){ i+=s; prepare(i); x[i]=w; while(i/=2) upd(i); } }; //N::push //pushしたあとはclearする //N::merge //Range add,min struct N{ int lz,mn; N(int v=inf):lz(0),mn(v){} bool add(int v){ mn+=v; lz+=v; return true; } void push(N&x,N&y){ x.add(lz); y.add(lz); lz=0; } static N merge(N x,N y){ return N(min(x.getm(),y.getm())); } int getm(){return mn;} }; struct T{ int l,r,t; }; bool over(T a,T b){ return max(a.l,b.l)<=min(a.r,b.r); } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); int n;cin>>n; int m;cin>>m; vi a=readvi(m,-1); vvc<int> qs(m); int q;cin>>q; rep(i,q){ int x;cin>>x; x--; qs[x].pb(i); } vc<T> pre{{0,q-1,-1}}; rep(i,m){ vc<T> cur; { int x=0; int p=a[i]; rep(j,si(qs[i])){ cur.pb({x,qs[i][j],p++}); x=qs[i][j]; } cur.pb({x,q-1,p++}); } int s=si(cur); vi base(s),val(s); { int k=0; rep(j,s){ k--; chmax(k,int(0)); while(k<si(pre)){ if(cur[j].r<pre[k].l)break; if(over(pre[k],cur[j])){ chmax(base[j],pre[k].t+1); } k++; } val[j]=cur[j].t-base[j]; } } if(*min_element(all(val))<0)no(); segbeats<N> seg(val); rng(j,1,s){ seg.ch(j,s,&N::add,-2); if(seg.get(j,s,&N::getm,[](int x,int y){return min(x,y);},inf)<0) seg.ch(j,s,&N::add,2); } vc<N> res; seg.enumerate(0,s,res); rep(j,s){ cur[j].t=base[j]+res[j].mn; if(cur[j].t>=n)no(); } pre=cur; } yes(); }