Dが難しすぎてCがクソゲー。レッドコーダー的にはつまらないセット。
| A | B | C | D | E | Place |
|---|---|---|---|---|---|
| 00:03 | 00:18 | 01:42 (+1) | - | - | 51st |
A:
簡単すぎて逆に焦るやつ
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int main(){ int a,b;scanf("%d%d",&a,&b); int ans=9999999; for(int i=0;i<b;i++){ int p,q;scanf("%d%d",&p,&q); ans=min(ans,q-p+1); } printf("%d\n",ans); for(int i=0;i<a;i++){ if(i)printf(" "); printf("%d",i%ans); } printf("\n"); }
B:
木をDFSしたときにd[深さ]=距離みたいな配列にすると、どこまでいけるか二分探索できる。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int c[210000]; vector<pair<int,int> >g[210000]; long long tmp[210000]; int par[210000]; int ans[210000]; void dfs(int a,int b){ for(int i=0;i<g[a].size();i++){ tmp[b+1]=tmp[b]+g[a][i].second; par[b+1]=g[a][i].first; dfs(g[a][i].first,b+1); ans[a]+=ans[g[a][i].first]; } long long L=tmp[b]-c[a]; int at=lower_bound(tmp,tmp+b+1,L)-tmp; ans[a]++; if(at)ans[par[at-1]]--; } int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",c+i); for(int i=0;i<a-1;i++){ int p,q;scanf("%d%d",&p,&q); p--; g[p].push_back(make_pair(i+1,q)); } dfs(0,0); for(int i=0;i<a;i++){ if(i)printf(" "); printf("%d",ans[i]-1); } printf("\n"); }
C:
setで範囲を持って頑張って更新するだけ。何が面白いのかさっぱりわからない上、(こういう明らかに定数つきそうな問題のくせして)定数倍がきつくpretest後に落ちる。時々writerが犯す、コンテストを機械的に難しくするミスの一種。本番出てなくてよかった。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int f[310000]; long long c[310000]; int segtree[1048576]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return 0; if(c<=a&&b<=d)return segtree[e]; return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1)); } void update(int a,int b){ a+=524288; segtree[a]=b; a/=2; while(a){ segtree[a]=max(segtree[a*2],segtree[a*2+1]); a/=2; } } set<pair<pair<int,int>,int> >S; set<pair<int,int> >T; set<pair<int,int> >Tinv; typedef set<pair<pair<int,int>,int> >::iterator wolf; inline int sig(long long a){ if(a<0)return -1; if(a==0)return 0; return 1; } int n; void add(int a,int b){ int sc=sig(c[a]); int tc=sig(c[a]+b); c[a]+=b; if(sc==tc)return; wolf it=S.upper_bound(make_pair(make_pair(a,mod),0)); it--; pair<pair<int,int>,int> p=(*it); if(p.first.first<a)S.insert(make_pair(make_pair(p.first.first,a),sc)); S.insert(make_pair(make_pair(a,a+1),tc)); if(a+1<p.first.second)S.insert(make_pair(make_pair(a+1,p.first.second),sc)); S.erase(p); wolf it2=S.upper_bound(make_pair(make_pair(p.first.first-1,mod),0)); if(it2!=S.begin())it2--; if(it2!=S.begin())it2--; vector<pair<pair<int,int>,int> >que; vector<pair<int,int> > del2; for(;it2!=S.end()&&(*it2).first.first<=a+1;it2++){ que.push_back(*it2); } int last=0; int len=0; int col=-2; vector<pair<pair<int,int>,int> >del; for(int i=0;i<que.size();i++){ update(que[i].first.first,0); if(que[i].second!=col){ if(col!=-2&&len>1){ S.insert(make_pair(make_pair(last,que[i].first.first),col)); for(int j=0;j<del.size();j++)S.erase(del[j]); } del.clear(); len=0; last=que[i].first.first; col=que[i].second; } del.push_back(que[i]); len++; } if(len>1){ S.insert(make_pair(make_pair(last,que[que.size()-1].first.second),col)); for(int j=0;j<del.size();j++)S.erase(del[j]); } wolf it4=S.lower_bound(make_pair(make_pair(que[0].first.first,0),-mod)); for(;it4!=S.end()&&(*it4).first.first<=a+1;it4++){ pair<pair<int,int>,int> d=(*it4); if(d.second==0)continue; int le=d.first.second-d.first.first; if(d.second==1){ it4++; if(d.first.second<n-1&&(*it4).second==-1)le+=(*it4).first.second-(*it4).first.first; it4--; } // T.insert(make_pair(le,d.first.first)); // Tinv.insert(make_pair(d.first.first,le)); update(d.first.first,le); } // for(wolf i=S.begin();i!=S.end();i++)printf("%d %d: %d\n",(*i).first.first,(*i).first.second,(*i).second); //for(int i=0;i<n;i++)printf("%d ",segtree[524288+i]); //printf("\n"); } int main(){ int a;scanf("%d",&a); n=a; for(int i=0;i<a;i++)scanf("%d",f+i); if(a==1){ int q;scanf("%d",&q); while(q--)printf("1\n");return 0; } for(int i=0;i<a-1;i++)c[i]=f[i+1]-f[i]; int len=0; int cur=-2; for(int i=0;i<a-1;i++){ int v=sig(c[i]); if(v!=cur){ if(len)S.insert(make_pair(make_pair(i-len,i),cur)); len=0;cur=v; } len++; } S.insert(make_pair(make_pair(a-1-len,a-1),cur)); for(wolf it=S.begin();it!=S.end();it++){ if((*it).second==0)continue; if((*it).second==1){ int le=(*it).first.second-(*it).first.first; wolf tmp=it; tmp++; if(tmp!=S.end()&&(*tmp).second==-1)le+=(*tmp).first.second-(*tmp).first.first; // T.insert(make_pair(le,(*it).first.first)); // Tinv.insert(make_pair((*it).first.first,le)); update((*it).first.first,le); }else{ // T.insert(make_pair((*it).first.second-(*it).first.first,(*it).first.first)); // Tinv.insert(make_pair((*it).first.first,(*it).first.second-(*it).first.first)); update((*it).first.first,(*it).first.second-(*it).first.first); } } int Q;scanf("%d",&Q); while(Q--){ int p,q,r;scanf("%d%d%d",&p,&q,&r); p--; if(p>=1)add(p-1,r); if(q<a)add(q-1,-r); printf("%d\n",segtree[1]+1); } }
D:
時間がなくて全然考えてないけど (p,?) と (?,q) の割り当て問題？ また今度。これも復元が無駄に付いてる気がするんだけど......。
