JOI2017本選
aojに問題が上がった時のためにコードを保存しておきます
1問目
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;} int N,Q,S,T; int A[222222]; signed main(){ scanf("%lld%lld%lld%lld",&N,&Q,&S,&T); rep(i,N+1)scanf("%lld",&A[i]); rep(i,N)A[i]=A[i+1]-A[i]; int ans=0; rep(i,N){ if(A[i]<0)ans+=A[i]*T; else ans+=A[i]*S; } rep(i,Q){ int l,r,x; scanf("%lld%lld%lld",&l,&r,&x); l--; if(A[l]<0)ans-=A[l]*T; else ans-=A[l]*S; A[l]+=x; if(A[l]<0)ans+=A[l]*T; else ans+=A[l]*S; if(r!=N){ if(A[r]<0)ans-=A[r]*T; else ans-=A[r]*S; A[r]-=x; if(A[r]<0)ans+=A[r]*T; else ans+=A[r]*S; } printf("%lld\n",-ans); } return 0; }
2問目
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;} int N,M,K; int A,B,C,T; int S[3333]; signed main(){ scanf("%lld%lld%lld",&N,&M,&K); scanf("%lld%lld%lld%lld",&A,&B,&C,&T); rep(i,M)scanf("%lld",&S[i]),S[i]--; S[M]=S[M-1]+1; vint v; int ans=0; rep(i,M){ if(i*B>T)break; int t=0; for(int j=0;j<=K;j++){ if(t==S[i+1]-S[i]||S[i]*B+t*C>T)break; int s=min(S[i+1]-S[i]-t,(T-S[i]*B-t*C)/A+1); if(j==0)ans+=s; else v.pb(s); t+=s; } } sort(all(v));reverse(all(v)); for(int i=0;i<v.size()&&i<K-M;i++)ans+=v[i]; cout<<ans-1<<endl; return 0; }
3問目
todo:二分探索しないで解く
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;} int H,W; int A[2222][2222]; int ma; int idx[2222]; bool C(int d){ int lim=ma-d; for(int i=0;i<H;i++){ idx[i]=0; for(int j=0;j<W;j++){ if(A[i][j]<lim)break; idx[i]++; } if(i)chmin(idx[i],idx[i-1]); int latte=-1; rep(j,W)if(A[i][j]==ma)latte=j+1; if(latte>idx[i])return false; } int l=INT_MAX,r=0; rep(i,H){ for(int j=idx[i];j<W;j++){ chmin(l,A[i][j]); chmax(r,A[i][j]); } } return r-l<=d; } int ans; void solve(){ int lb=-1,ub=1000000000; while(ub-lb>1){ int mid=(ub+lb)/2; if(C(mid))ub=mid; else lb=mid; } chmin(ans,ub); } signed main(){ scanf("%lld%lld",&H,&W); rep(i,H)rep(j,W)scanf("%lld",&A[i][j]),chmax(ma,A[i][j]); ans=INT_MAX; rep(i,2){ rep(j,2){ solve(); rep(k,H)reverse(A[k],A[k]+W); } rep(l,W){ for(int k=0;k<H/2;k++)swap(A[k][l],A[H-1-k][l]); } } cout<<ans<<endl; return 0; }
4問目
todo:考察して
5問目
todo:seg木で甘えてる部分を線形(もしくはsortとかのlog)にする
これは罠で、seg木で通ればもうそれでいいや
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;} struct segtree{ static const int SEG=1<<20; vint dat; segtree():dat(SEG*2){} void update(int k,int x){ k+=SEG-1; dat[k]=x; while(k){ k=(k-1)/2; dat[k]=max(dat[k*2+1],dat[k*2+2]); } } int get(int a,int b,int k=0,int l=0,int r=SEG){ if(r<=a||b<=l)return 0; if(a<=l&&r<=b)return dat[k]; return max(get(a,b,k*2+1,l,(l+r)/2),get(a,b,k*2+2,(l+r)/2,r)); } }; int N,M; int C[1111111]; int cnt[1111111]; int base[1111111]; vint G[1111111]; int ans[1111111]; signed main(){ scanf("%lld%lld",&N,&M); rep(i,N)scanf("%lld",&C[i]),C[i]--; rep(i,N)cnt[C[i]]++; fill_n(ans,M,N); rep(lattemalta,2){ rep(i,M)G[i].clear(); memset(base,0,sizeof(base)); segtree seg; rep(i,M)seg.update(i,cnt[i]); vint b; if(lattemalta==1)b.pb(C[0]); int cur=lattemalta; while(cur+1<N){ if(C[cur]==C[cur+1]){ base[C[cur]]+=2; } else{ G[C[cur]].pb(C[cur+1]); G[C[cur+1]].pb(C[cur]); } cur+=2; } if(cur>N)b.pb(C[N-1]); rep(i,M){ int a=N-cnt[i]; int cost=G[i].size(); for(auto t:G[i]){ cnt[t]--; a--; seg.update(t,cnt[t]); } int tmp=0; if(i)tmp=seg.get(0,i); if(i+1!=M)chmax(tmp,seg.get(i+1,M)); chmin(ans[i],cost+a-tmp); for(auto t:G[i]){ cnt[t]++; seg.update(t,cnt[t]); } } } rep(i,M)printf("%lld\n",ans[i]); return 0; }
