Submission #841244

#TimeUsernameProblemLanguageResultExecution timeMemory
841244maroonrkRadio Towers (IOI22_towers)C++17
100 / 100
1314 ms202884 KiB
#include "towers.h" #ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #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> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} 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<<"}"; } 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; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class t> void print_single(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } template<class t,class u> void print_single(const pair<t,u>&p,int suc=1){ print_single(p.a,2); print_single(p.b,suc); } template<class T> void print_single(const vector<T>&v,int suc=1){ rep(i,v.size()) print_single(v[i],i==int(v.size())-1?suc:2); } template<class T> void print_offset(const vector<T>&v,ll off,int suc=1){ rep(i,v.size()) print_single(v[i]+off,i==int(v.size())-1?suc:2); } template<class T,size_t N> void print_single(const array<T,N>&v,int suc=1){ rep(i,N) print_single(v[i],i==int(N)-1?suc:2); } template<class T> void print(const T&t){ print_single(t); } template<class T,class ...Args> void print(const T&t,const Args&...args){ print_single(t,2); print(args...); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } //#define CAPITAL /* void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif }*/ void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } 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 topbit(ull 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 botbit(ull a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } int popcount(ull t){ return __builtin_popcountll(t); } int bitparity(ll t){ return __builtin_parityll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } ull umask(int i){ return (ull(1)<<i)-1; } ll minp2(ll n){ if(n<=1)return 1; else return ll(1)<<(topbit(n-1)+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); } ll rand_int(ll k){ //[0,k) return rand_int(0,k-1); } 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; } template<class t> bool bis(const vc<t>&v,const t&a){ return binary_search(all(v),a); } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } template<class t> vc<t> presum(const vc<t>&a){ vc<t> s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } vc<ll> presum(const vi&a){ vc<ll> s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } //BIT で数列を管理するときに使う (CF850C) template<class t> vc<t> predif(vc<t> a){ gnr(i,1,si(a))a[i]-=a[i-1]; return a; } template<class t> vvc<ll> imos(const vvc<t>&a){ int n=si(a),m=si(a[0]); vvc<ll> b(n+1,vc<ll>(m+1)); rep(i,n)rep(j,m) b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]; return b; } //verify してないや void transvvc(int&n,int&m){ swap(n,m); } template<class t,class... Args> void transvvc(int&n,int&m,vvc<t>&a,Args&...args){ assert(si(a)==n); vvc<t> b(m,vi(n)); rep(i,n){ assert(si(a[i])==m); rep(j,m)b[j][i]=a[i][j]; } a.swap(b); transvvc(n,m,args...); } //CF854E void rotvvc(int&n,int&m){ swap(n,m); } template<class t,class... Args> void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){ assert(si(a)==n); vvc<t> b(m,vi(n)); rep(i,n){ assert(si(a[i])==m); rep(j,m)b[m-1-j][i]=a[i][j]; } a.swap(b); rotvvc(n,m,args...); } //ソートして i 番目が idx[i] //CF850C template<class t> vi sortidx(const vc<t>&a){ int n=si(a); vi idx(n);iota(all(idx),0); sort(all(idx),[&](int i,int j){return a[i]<a[j];}); return idx; } //vs[i]=a[idx[i]] //例えば sortidx で得た idx を使えば単にソート列になって返ってくる //CF850C template<class t> vc<t> a_idx(const vc<t>&a,const vi&idx){ int n=si(a); assert(si(idx)==n); vc<t> vs(n); rep(i,n)vs[i]=a[idx[i]]; return vs; } //CF850C vi invperm(const vi&p){ int n=si(p); vi q(n); rep(i,n)q[p[i]]=i; return q; } template<class t,class s=t> s SUM(const vc<t>&a){ return accumulate(all(a),s(0)); } template<class t> t MAX(const vc<t>&a){ return *max_element(all(a)); } template<class t> pair<t,int> MAXi(const vc<t>&a){ auto itr=max_element(all(a)); return mp(*itr,itr-a.bg); } template<class t> t MIN(const vc<t>&a){ return *min_element(all(a)); } template<class t> pair<t,int> MINi(const vc<t>&a){ auto itr=min_element(all(a)); return mp(*itr,itr-a.bg); } template<class t,class u> pair<t,u> operator+(const pair<t,u>&a,const pair<t,u>&b){ return mp(a.a+b.a,a.b+b.b); } vi vid(int n){ vi res(n);iota(all(res),0); return res; } template<class S> S revv(S s){ reverse(all(s)); return s; } pi operator+(pi a,pi b){return pi(a.a+b.a,a.b+b.b);} template<class t> t gpp(vc<t>&vs){ assert(si(vs)); t res=move(vs.back()); vs.pop_back(); return res; } template<class t> void pb(vc<t>&a,const vc<t>&b){ a.insert(a.ed,all(b)); } template<class t> vc<t> cat(vc<t> a,const vc<t>&b){ pb(a,b); return a; } template<class t,class u> vc<t>& operator+=(vc<t>&a,u x){ for(auto&v:a)v+=x; return a; } template<class t,class u> vc<t> operator+(vc<t> a,u x){ return a+=x; } template<class t,class u> vc<t>& operator-=(vc<t>&a,u x){ for(auto&v:a)v-=x; return a; } template<class t,class u> vc<t>& operator-(vc<t> a,u x){ return a-=x; } //N() が単位元 //VERIFY: yosupo //CF407E template<class N> struct segtree{ vc<N> x; int n,s; segtree(){} template<class t> segtree(const vc<t>&a){ 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) x[i]=N::merge(x[i*2],x[i*2+1]); } //NOT Verified segtree(int nn){ resize(nn); } void resize(int nn){ n=nn; s=1; while(s<n){s*=2;} x.assign(s*2,N()); gnr(i,1,s) x[i]=N::merge(x[i*2],x[i*2+1]); } template<class t> void load(const vc<t>&a){ n=a.size(); s=1; while(s<n){s*=2;} x.resize(s*2); rep(i,n) x[s+i]=N(a[i]); rng(i,n,s) x[s+i]=N(); gnr(i,1,s) x[i]=N::merge(x[i*2],x[i*2+1]); } void clear(){ rep(i,n) x[s+i]=N(); gnr(i,1,s) x[i]=N::merge(x[i*2],x[i*2+1]); } N point_get(int i){ assert(inc(0,i,n-1)); return x[i+s]; } void point_set(int i,const N&t){ assert(inc(0,i,n-1)); i+=s; x[i]=t; while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]); } void point_merge(int i,const N&t){ assert(inc(0,i,n-1)); i+=s; x[i]=N::merge(x[i],t); while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]); } template<class F,class...Args> void point_change(int i,F f,Args&&...args){ assert(inc(0,i,n-1)); i+=s; (x[i].*f)(forward<Args>(args)...); while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]); } N composite(int b,int e){ assert(0<=b&&b<=e&&e<=n); N lf,rt; for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){ if (l&1){ lf=N::merge(lf,x[l]); l++; } if (r&1){ r--; rt=N::merge(x[r],rt); } } return N::merge(lf,rt); } N getall(){ return x[1]; } //UTPC2020E //n 超えるかもしれない template <class F,class... Args> pair<int,N> max_right(int l,F f,Args&&... args){ assert((N().*f)(forward<Args>(args)...)); assert(0<=l&&l<=n); if(l==n)return mp(n,N()); l+=s; N sm; assert((sm.*f)(forward<Args>(args)...)); do { while (l % 2 == 0) l >>= 1; if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){ while (l < s) { l = (2 * l); N tmp=N::merge(sm,x[l]); if ((tmp.*f)(forward<Args>(args)...)) { sm = tmp; l++; } } return mp(l - s,sm); } sm = N::merge(sm, x[l]); l++; } while ((l & -l) != l); return mp(n,sm); } //UTPC2020E template <class F,class... Args> pair<int,N> min_left(int r,F f,Args&&... args){ assert((N().*f)(forward<Args>(args)...)); assert(0<=r&&r<=n); if(r==0)return mp(0,N()); r+=s; N sm; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) { while (r < s) { r = (2 * r + 1); N tmp=N::merge(x[r],sm); if ((tmp.*f)(forward<Args>(args)...)) { sm = tmp; r--; } } return mp(r + 1 - s,sm); } sm = N::merge(x[r], sm); } while ((r & -r) != r); return mp(0,sm); } //行列とか乗せて必要なのはベクトルとの積,みたいなときに使える? //CF Goodbye 2016 E template<class F,class T> T accumulate(int l, int r,F f,T t) { assert(0<=l&&l<=r&&r<=s); if (l == r) return t; l+=s; r+=s; static int buf[2][30]; int cnt[2]{}; { int l2 = l, r2 = r; while (l < r) { if (l & 1){ //(x[l++].*f)(forward<Args>(args)...); buf[0][cnt[0]++]=l++; } if (r & 1){ //(x[--r].*f)(forward<Args>(args)...); buf[1][cnt[1]++]=--r; } l >>= 1; r >>= 1; } l = l2; r = r2; } rep(i,cnt[0])t=(x[buf[0][i]].*f)(t); per(i,cnt[1])t=(x[buf[1][i]].*f)(t); return t; } }; //最も基本的な動的 segtree //ByteCamp 2022 Day4 I template<class N> struct psegtree{ struct N2{ N v; int l,r; }; vc<N2> x; int L,s; template<class t> psegtree(const vc<t>&a,int foresight=0):x(foresight){ x.clear(); int n=a.size(); L=0; while((1<<L)<n)L++; s=1<<L; x.resize(s*2,{N(),0,0}); rep(i,n)x[s+i].v=N(a[i]); gnr(i,1,s){ x[i].v=N::merge(x[i*2].v,x[i*2+1].v); x[i].l=i*2; x[i].r=i*2+1; } } psegtree(int foresight=0):x(foresight){} int init(int n){ x.clear(); L=0; while((1<<L)<n)L++; s=1<<L; int a=nl(N()); rep(i,L)a=nn(a,a); return a; } int nl(const N&val){ x.pb({val,-1,-1}); return si(x)-1; } int nn(int l,int r){ x.pb({N::merge(x[l].v,x[r].v),l,r}); return si(x)-1; } int point_set(int root,int i,const N&val){ static int buf[40]; rep(lv,L){ buf[lv]=root; if((i>>(L-1-lv))&1)root=x[root].r; else root=x[root].l; } int res=nl(val); per(lv,L){ int j=buf[lv]; if((i>>(L-1-lv))&1){ res=nn(x[j].l,res); }else{ res=nn(res,x[j].r); } } return res; } int point_merge(int root,int i,const N&val){ static int buf[40]; rep(lv,L){ buf[lv]=root; if((i>>(L-1-lv))&1)root=x[root].r; else root=x[root].l; } int res=nl(N::merge(x[root].v,val)); per(lv,L){ int j=buf[lv]; if((i>>(L-1-lv))&1){ res=nn(x[j].l,res); }else{ res=nn(res,x[j].r); } } return res; } N compositedfs(int root,int l,int r,int b,int e){ if(e<=l||r<=b)return N(); if(b<=l&&r<=e)return x[root].v; int mid=(l+r)/2; return N::merge(compositedfs(x[root].l,l,mid,b,e),compositedfs(x[root].r,mid,r,b,e)); } N composite(int root,int b,int e){ assert(b<=e); if(b==e)return N(); return compositedfs(root,0,s,b,e); } }; struct MaxNode{ int v; MaxNode(int vv=-inf):v(vv){} static MaxNode merge(const MaxNode&a,const MaxNode&b){ return MaxNode(max(a.v,b.v)); } bool ok(int x){return v<x;} }; struct MinNode{ pi v; MinNode(pi vv=pi(inf,-1)):v(vv){} static MinNode merge(const MinNode&a,const MinNode&b){ return MinNode(min(a.v,b.v)); } }; struct SumNode{ int v; SumNode(int vv=0):v(vv){} static SumNode merge(const SumNode&a,const SumNode&b){ return SumNode(a.v+b.v); } }; segtree<MinNode> minseg; psegtree<SumNode> z; vi ls[2]; void init(int n,vi h){ vc<pi> hi(n); rep(i,n)hi[i]=pi(h[i],i); minseg.load(hi); int root=z.init(ten(9)); rep(phase,2){ dmp(phase); segtree<MaxNode> mx(h); ls[phase].resize(n); int cur=root; auto add=[&](int i,int v){ if(i<0)return; dmp2(i,v); cur=z.point_merge(cur,i,v); }; vi pos; rep(i,n){ dmp(i); while(si(pos)&&h[pos.back()]>h[i]){ int j=gpp(pos); dmp2(i,j); int v=mx.composite(j+1,i).v; if(si(pos)){ int k=pos.back(); int w=mx.composite(k+1,j).v; add(w-h[j],-1); chmin(v,w); } add(v-h[j],1); } if(si(pos)){ int k=pos.back(); int w=mx.composite(k+1,i).v; add(w-h[i],1); } pos.pb(i); ls[phase][i]=cur; } reverse(all(h)); } reverse(all(ls[1])); } int max_towers(int l,int r,int d){ int m=minseg.composite(l,r+1).v.b; dmp2(l,m,r); int ans=0; ans+=z.composite(ls[0][r],d,z.s).v; ans-=z.composite(ls[0][m],d,z.s).v; dmp(ans); ans+=z.composite(ls[1][l],d,z.s).v; ans-=z.composite(ls[1][m],d,z.s).v; dmp(ans); ans++; dmp(ans); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...