Codeforces Round #808 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

1708A — Difference Operations

Solution

Code

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long

const LL MOD = 1e9 + 7;
const int MX = 1e5 + 23;

int read(){
	char k = getchar(); LL x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
	return x;
}

int n ,a[MX];
void solve(){
	n = read();
	for(int i = 1 ; i <= n ; ++i) a[i] = read();
	int ok = 1;
	for(int i = 1 ; i <= n ; ++i){
		if(a[i] % a[1]) ok = false;
	}
	puts(ok ? "YES" : "NO");
}

int main(){
	int T = read();
	while(T--) solve();
	return 0;
}

1708B — Difference of GCDs

idea: waaitg

Solution

Code

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
	freopen(#x".in" ,"r" ,stdin);\
	freopen(#x".out" ,"w" ,stdout)
#define LL long long

const int MX = 1e5 + 23;
const LL MOD = 998244353;

int read(){
	char k = getchar(); int x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
	return x;
}

int a[MX];
void solve(){
	int n = read() ,l = read() ,r = read();
	int ok = 1;
	for(int i = 1 ; i <= n ; ++i){
		a[i] = ((l - 1) / i + 1) * i;
		ok = ok && a[i] <= r;
	}
	if(ok){
		puts("YES");
		for(int i = 1 ; i <= n ; ++i)
			printf("%d%c" ,a[i] ," \n"[i == n]);
	}
	else puts("NO");
}

int main(){
	int T = read();
	for(int i = 1 ; i <= T ; ++i){
		solve();
	}
	return 0;
}

1707A — Doremy's IQ

idea: Imakf

Solution

Code of solution 1

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
	freopen(#x".in" ,"r" ,stdin);\
	freopen(#x".out" ,"w" ,stdout)
#define LL long long

const int MX = 5e5 + 23;
const LL MOD = 998244353;

int read(){
	char k = getchar(); int x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
	return x;
}

int n ,a[MX] ,q ,choose[MX];
bool check(int mid){
	for(int i = 1 ; i <= n ; ++i) choose[i] = 0;
	int iq = q;
	for(int i = 1 ; i < mid ; ++i)
		if(a[i] <= iq) choose[i] = 1;
	for(int i = mid ; i <= n ; ++i){
		choose[i] = 1;
		if(iq == 0) return 0;
		if(a[i] > iq) --iq;
		
	}
	if(iq < 0) return 0;
	return 1;
}

void solve(){
	n = read() ,q = read();
	for(int i = 1 ; i <= n ; ++i)
		a[i] = read();
	int l = 1 ,r = n ,mid;
	while(l <= r){
		mid = (l + r) >> 1;
		if(check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	// [r + 1 ,n] is selected
	check(r + 1);
	for(int i = 1 ; i <= n ; ++i)
		printf("%d" ,choose[i]);
	puts("");
}

int main(){
	int T = read();
	for(int i = 1 ; i <= T ; ++i){
		solve();
	}
	return 0;
}

Code of solution 2

By waaitg

#include<cstdio>
int a[100005],b[100005];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,iq;
		scanf("%d%d",&n,&iq);
		for(int i=1;i<=n;++i)
			scanf("%d",&a[i]);
		int sum=0,nq=0;
		for(int i=n;i>=1;--i){
			if(a[i]<=nq)b[i]=1;
			else if(nq<iq)++nq,b[i]=1; 
			else b[i]=0;
		} 
		for(int i=1;i<=n;++i)
			printf("%d",b[i]);
		puts("");
	}
	return 0;
}

1707B — Difference Array

idea: Imakf and waaitg

Unfortunately, a harder version of this problem has appeared in a codechef contest here.

In fact, this problem was come up with more than 1 year ago, earlier than the problem in that codechef contest. We are sorry again.

Solution

Code

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
const int maxn=100005;
int a[maxn];
int main(){
	int T;read(T);
	while(T--){
		int n;read(n);
		for(int i=1;i<=n;++i)read(a[i]);
		for(int i=n-1;i>=1;--i){
			int pre=a[i+1],ok=false;
			for(int j=i;j>=1;--j){
				ok=(a[j]==0);
				pre-=(a[j]=pre-a[j]);
				if(ok){
					sort(a+j,a+i+1);
					break;
				}
			}
			if(!ok)
				sort(a+1,a+i+1);
		}
		write(a[1]),pc('\n');
	}
	return 0;
}
/*
_|_|_|_|        _|_|      _|      _|   _|_|_|_|_|   _|_|_|_|_|   _|
_|      _|    _|    _|    _|_|    _|       _|       _|           _|
_|      _|   _|      _|   _| _|   _|       _|       _|           _|
_|      _|   _|_|_|_|_|   _|  _|  _|       _|       _|_|_|_|_|   _|
_|      _|   _|      _|   _|   _| _|       _|       _|           _|
_|      _|   _|      _|   _|    _|_|       _|       _|           _|
_|_|_|_|     _|      _|   _|      _|   _|_|_|_|_|   _|_|_|_|_|   _|_|_|_|_|

_|_|_|_|_|   _|      _|   _|_|_|_|     _|      _|
    _|        _|    _|    _|      _|    _|    _|
    _|         _|  _|     _|      _|     _|  _|
    _|          _|_|      _|      _|      _|_|
    _|         _|  _|     _|      _|       _|
    _|        _|    _|    _|      _|       _|
    _|       _|      _|   _|_|_|_|         _|

_|             _|_|_|     _|      _|   _|_|_|_|_|
_|           _|      _|   _|      _|   _|
_|           _|      _|    _|    _|    _|
_|           _|      _|    _|    _|    _|_|_|_|_|
_|           _|      _|     _|  _|     _|
_|           _|      _|      _|_|      _|
_|_|_|_|_|     _|_|_|         _|       _|_|_|_|_|

_|_|_|_|_|   _|      _|   _|_|_|_|_|
    _|        _|    _|        _|
    _|         _|  _|         _|
    _|          _|_|          _|
    _|           _|           _|
    _|           _|           _|
    _|           _|           _|

Created by xiaolilsq.
*/

1707C — DFS Trees

idea: waaitg

Solution

Code

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
const int maxn=100005,maxm=200005;
int par[maxn];
int AC(int x){
	return par[x]==x?x:par[x]=AC(par[x]);
}
struct Edge{
	int v,nt;
	Edge(int v=0,int nt=0):
		v(v),nt(nt){}
}e[maxn*2],es[maxm];
int hd[maxn],num;
void qwq(int u,int v){
	e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dp[maxn];
int pa[maxn][20];
void dfs(int u,int p){
	pa[u][0]=p;
	for(int j=1;(1<<j)<=dp[u];++j)
		pa[u][j]=pa[pa[u][j-1]][j-1];
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p)continue;
		dp[v]=dp[u]+1;dfs(v,u);
	}
}
int jump(int x,int t){
	for(int cn=0;t;t>>=1,++cn)
		if(t&1)x=pa[x][cn];
	return x;
}
int lca(int x,int y){
	if(dp[x]>dp[y])x=jump(x,dp[x]-dp[y]);
	if(dp[y]>dp[x])y=jump(y,dp[y]-dp[x]);
	if(x==y)return x;
	for(int t=19;t>=0;--t)
		if(pa[x][t]!=pa[y][t])
			x=pa[x][t],y=pa[y][t];
	return pa[x][0];
}
int vis[maxn];
char s[maxn];
void pushdown(int u,int p){
	if(vis[u]==0)s[u]='1';
	else s[u]='0';
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p)continue;
		vis[v]+=vis[u];
		pushdown(v,u);
	}
}
int main(){
	int n,m;
	read(n),read(m);
	for(int i=1;i<=n;++i)
		par[i]=i;
	int tp=0;
	for(int i=1;i<=m;++i){
		int u,v;
		read(u),read(v);
		if(AC(u)==AC(v)){
			es[++tp]=Edge(u,v);
		}
		else{
			par[AC(u)]=AC(v);
			qwq(u,v),qwq(v,u);
		}
	}
	int root=1;
	dfs(root,0);
	for(int i=1;i<=tp;++i){
		int u=es[i].v,v=es[i].nt;
		if(dp[u]>dp[v])u^=v^=u^=v;
		int w=lca(u,v);
		if(u==w){
			--vis[v];
			++vis[jump(v,dp[v]-dp[u]-1)];
		}
		else{
			++vis[root];
			--vis[u];
			--vis[v];
		}
	}
	pushdown(root,0);
	s[n+1]='\0';
	printf("%s\n",s+1);
	return 0;
}

1707D — Partial Virtual Trees

idea: Imakf and waaitg

Solution

Code

By Imakf

#include <bits/stdc++.h>
 
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
	freopen(#x".in" ,"r" ,stdin);\
	freopen(#x".out" ,"w" ,stdout)
#define LL long long
 
const int MX = 2000 + 23;
 
LL MOD;
 
using namespace std;
 
int read(){
	char k = getchar(); int x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
	return x;
}
 
int head[MX] ,tot = 1;
struct edge{
	int node ,next;
}h[MX << 1];
void addedge(int u ,int v ,int flg = 1){
	// if(flg) debug("%d %d\n" ,u ,v);
	h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
	if(flg) addedge(v ,u ,false);
}
 
int n ,dp[MX][MX] ,S[MX][MX] ,suf[MX][MX] ,pre[MX][MX];
void dapai(int x ,int f){
	int ch = 0;
	for(int i = head[x] ,d ; i ; i = h[i].next){
		if((d = h[i].node) == f) continue;
		dapai(d ,x);
	}
	for(int i = head[x] ,d ; i ; i = h[i].next){
		if((d = h[i].node) == f) continue;
		++ch;
		for(int j = 0 ; j <= n ; ++j){
			suf[ch][j] = pre[ch][j] = S[d][j];
		}
	}
 
	if(!ch){
		for(int i = 1 ; i <= n ; ++i){
			dp[x][i] = 1 % MOD;
			S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
		}
		return ;
	}
	for(int j = 0 ; j <= n ; ++j){
		for(int i = 1 ; i <= ch ; ++i)
			pre[i][j] = 1LL * pre[i][j] * pre[i - 1][j] % MOD;
		for(int i = ch ; i >= 1 ; --i)
			suf[i][j] = 1LL * suf[i][j] * suf[i + 1][j] % MOD;
	}
	for(int i = 1 ; i <= n ; ++i) dp[x][i] = pre[ch][i];
	if(x != 1) for(int i = head[x] ,d ,c = 0 ; i ; i = h[i].next){
		if((d = h[i].node) == f) continue;
		++c;
		LL sum = 0;
		for(int mx = 1 ; mx <= n ; ++mx){
			dp[x][mx] = (dp[x][mx] + sum * dp[d][mx]) % MOD;
			sum = (sum + 1LL * pre[c - 1][mx] * suf[c + 1][mx]) % MOD;
		}
	}
	for(int i = 1 ; i <= ch ; ++i)
		for(int j = 0 ; j <= n ; ++j)
			suf[i][j] = pre[i][j] = 1 % MOD;
	for(int i = 1 ; i <= n ; ++i)
		S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
}
 
int C[MX][MX];
void init(){
	for(int i = 0 ; i < MX ; ++i) C[i][0] = 1 % MOD;
	for(int i = 1 ; i < MX ; ++i)
		for(int j = 1 ; j < MX ; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
 
int main(){
    
    n = read() ,MOD = read();
	init();
	
	for(int i = 0 ; i < MX ; ++i)
		for(int j = 0 ; j < MX ; ++j)
			suf[i][j] = pre[i][j] = 1 % MOD;
			
	
	 
	for(int i = 2 ; i <= n ; ++i){
		addedge(read() ,read());
		// addedge(rand() % (i - 1) + 1 ,i);
	}
	
	dapai(1 ,0);
	
	for(int i = 1 ; i < n ; ++i){
		LL ans = 0;
		for(int j = 1 ; j <= i ; ++j){
			ans += ((i - j) & 1 ? -1LL : 1LL) * C[i][j] * dp[1][j] % MOD;
		}
		ans = (ans % MOD + MOD) % MOD;
		printf("%lld%c" ,ans ," \n"[i == n]);
	}
	return 0;
}

1707E — Replace

idea: Wolam, Imakf and waaitg

Solution

Code

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
	static char q[64];int cnt=0;
	if(x==0)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
const int maxn=100005,maxq=100005,maxt=34;
const int inf=0x3f3f3f3f;
int a[maxn];
struct Segment{
	int l,r;
	Segment(int l=inf,int r=-inf):
		l(l),r(r){}
	Segment operator * (const Segment o)const{
		return Segment(min(l,o.l),max(r,o.r));
	}
	bool operator != (const Segment o)const{
		return l!=o.l||r!=o.r;
	}
	void input(void){
		read(l),read(r);
	}
}sg[maxt][maxn],tr[maxn],qy[maxq];
int n;
void res(void){
	for(int i=1;i<n;++i)
		tr[i]=Segment();
}
void add(int p,Segment v){
	while(p<n){
		tr[p]=tr[p]*v;
		p+=(p&(-p));
	}
}
Segment ask(int p){
	Segment re;
	while(p){
		re=re*tr[p];
		p^=(p&(-p));
	}
	return re;
}
struct Edge{
	int v,w,nt;
	Edge(int v=0,int w=0,int nt=0):
		v(v),w(w),nt(nt){}
}e[maxn];
int num,hd[maxn];
void ins(int u,int v,int w){
	e[++num]=Edge(v,w,hd[u]),hd[u]=num;
}
int st[maxq],tp;
long long Ans[maxq];
int main(){
	int q;read(n),read(q);
	if(n==1){while(q--)puts("0");return 0;}
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<n;++i){
		 if(a[i]<=a[i+1])
		 	sg[0][i]=Segment(a[i],a[i+1]);
		else
			sg[0][i]=Segment(a[i+1],a[i]);
	}
	for(int i=1;i<maxt;++i){
		for(int j=1;j<n;++j){
			if(sg[i-1][j].l>=sg[i-1][j].r)sg[i][j]=Segment();
			else ins(sg[i-1][j].l,sg[i-1][j].r-1,j);
		}
		res();
		for(int j=n-1;j>=1;--j){
			add(j,sg[i-1][j]);
			for(int k=hd[j];k;k=e[k].nt){
				sg[i][e[k].w]=ask(e[k].v);
			}
			hd[j]=0;
		}
		num=0;
	}
	for(int i=1;i<=q;++i){
		qy[i].input();
		if(qy[i].l==qy[i].r)Ans[i]=-2;
		else ins(qy[i].l,qy[i].r-1,i);
	}
	res();
	for(int i=n-1;i>=1;--i){
		add(i,sg[maxt-1][i]);
		for(int j=hd[i];j;j=e[j].nt){
			if(i==1&&e[j].v==n-1)
				Ans[e[j].w]=-1;
			else if(ask(e[j].v)!=Segment(1,n))
				Ans[e[j].w]=-2;
			else
				st[++tp]=e[j].w;
		}
		hd[i]=0;
	}
	num=0;
	for(int i=maxt-2;~i;--i){
		for(int j=1;j<=tp;++j){
			ins(qy[st[j]].l,qy[st[j]].r-1,st[j]);
		}
		res();
		for(int j=n-1;j>=1;--j){
			add(j,sg[i][j]);
			for(int k=hd[j];k;k=e[k].nt){
				Segment tmp=ask(e[k].v);
				int id=e[k].w;
				if(tmp!=Segment(1,n))
					Ans[id]|=(1ll<<i),qy[id]=tmp;
			}
			hd[j]=0;
		}
		num=0;
	}
	for(int i=1;i<=q;++i)
		write(++Ans[i]),pc('\n');
	return 0;
}

1707F — Bugaboo

This is a noun almost one year ago when this problem came out.

idea: Imakf and waaitg

Solution

Code

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<assert.h>
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>void read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
const int maxn=20000005;
struct Count{
	int pos,val;
	Count(int pos=-1,int val=-1):
		pos(pos),val(val){}
};
int plus(int x,int y){
	return (x<0||y<0)?-1:x+y;
}
Count operator + (const Count A,const Count B){
	int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val);
	if(~Ap&&~Bp)return Ap^Bp?Count():Count(Ap|Bp,va);
	if(~Ap||~Bp)return Count(Ap&Bp,va);
	return Count(-1,va);
}
Count operator * (const Count A,const Count B){
	int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val);
	if(~Ap&&~Bp)return Count(Ap^Bp,va);
	if(~Ap||~Bp)return Count(-1,va);
	return Count(-1,plus(va,1));
}
int c[maxn];
int tn,Op[maxn],Cn[maxn];
Count dp[maxn];
int t,hb[maxn],rev[maxn];
void pushup(int p){
	int l=p<<1,r=l|1;
	dp[p]=((t&hb[p])?(dp[l]+dp[r]):(dp[l]*dp[r]));
}
int va1,sum;
void ins(int i){
	int p=rev[(i&(tn-1))];
	if(~c[i])Op[p]^=c[i];else ++Cn[p];
	if(dp[p+tn].pos>0)--va1;else sum-=dp[p+tn].val;
	dp[p+tn]=(Cn[p]?Count(-1,Cn[p]-1):Count(Op[p],0));
	if(dp[p+tn].pos>0)++va1;else sum+=dp[p+tn].val;
}
void del(int i){
	int p=rev[(i&(tn-1))];
	if(~c[i])Op[p]^=c[i];else --Cn[p];
}
int power(int a,int x,int p){
	if(x==-1)return 0;
	int re=1;
	while(x){
		if(x&1)re=1ll*re*a%p;
		a=1ll*a*a%p;x>>=1;
	}
	return re;
}
int main(){
	int n,m,w;
	read(n),read(m),read(t),read(w);
	memset(c,-1,sizeof c);
	for(int i=1;i<=m;++i){
		int d;read(d);--d;read(c[d]);
	}
	tn=(n&(-n));
	hb[0]=0;hb[1]=1;
	for(int i=2;i<tn*2;++i)
		hb[i]=(hb[i>>1]<<1);
	int cn=-1;for(;(1<<(cn+1))<tn;++cn);
	for(int i=1;i<tn;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<cn);
	for(int i=0;i<tn;++i)dp[i+tn].val=0;
	for(int i=0;i<n;++i)ins(i);
	if(t<tn)for(int i=tn-1;i>=1;--i)pushup(i);
	int q;read(q);
	while(q--){
		int f;read(f);--f;
		del(f);read(c[f]);ins(f);
		int p;read(p);
		if(t>=tn){
			write(va1?0:power((1<<w)%p,sum,p));
		}
		else{
			int now=(rev[(f&(tn-1))]|tn);while(now>>=1)pushup(now);
			write(power((1<<w)%p,plus(dp[1].val,dp[1].pos==-1),p));
		}
		pc('\n');
	}
	return 0;
}

	Rev.	Lang.	By	When	Δ	Comment
	en2		waaitg	2022-07-16 20:04:10	264	Tiny change: 'ion">\n\n[tutoria' -> 'ion">\n\n[problem:1707A]\n[tutoria'
	en1		waaitg	2022-07-16 19:41:35	17872	Initial revision (published)

History