Title Link: Educational Codeforces Round 80 (Rated for Div. 2)

A: It's obviously a double channel function, but there are some rounding things that lead to small deviations. But we don't need O(1) to do it at all. We know that the minimum value must be near sqrt(d), so a little violence is enough.

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,d;
inline void solve(){
	cin>>n>>d;	int l=max((int)sqrt(d)-1000,0LL),r=2*sqrt(d)+1000,res=1e14;
	for(int i=l;i<=r;i++){
		res=min(res,(int)(i+ceil(d*1.0/(i+1))));
	}
	if(res<=n)	puts("YES");
	else	puts("NO");
}
signed main(){
	cin>>T;
	while(T--)	solve();
	return 0;
}

b: If the number of bits of b is x, then we can get a * pow(10,x) + b = a * b + a + b, so b is 9,99999...

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,T;
inline void solve(){
	cin>>a>>b;	int t=9,res=0;
	while(t<=b){
		res+=a;	t=t*10+9;
	}
	cout<<res<<endl;
}
signed main(){
	cin>>T;
	while(T--)	solve();
	return 0;
}

C: We can find that when the last bit satisfies the condition, the whole sequence satisfies the condition. So we preprocess the number of non strict LIS whose length is j and i numbers can be selected at present.

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
int n,m,dp[20][1010],res;
void init(){
	for(int i=1;i<=n;i++)	dp[0][i]=1;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=j;k++)	dp[i][j]=(dp[i][j]+dp[i-1][k])%p;
}
signed main(){
	cin>>n>>m;	init();
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			res=(res+dp[m-1][i]*dp[m-1][n-j+1]%p)%p;
		}
	}
	cout<<res;
	return 0;
}

D: The minimum value is the maximum. First, consider the binary answer. For example, if the current dichotomy answer is mid, the size of the number itself is not important. We only focus on whether it is greater than or equal to mid, so if we set the greater than or equal to 1 and the less than to 0, then we can compress the state. As long as there are two states or operations of 1 < < M-1, it is legal. If 1 < < m - 1 is set as s, then we can find out whether s^x exists for each state x, but there is a problem that a certain state may contain x ^ s rather than s^x alone, so we can set all that contain and exist as 1.

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int n,m,a[N][9],st[1<<8],l,r=1e9,res1=1,res2=1;
inline int check(int mid){
	memset(st,0,sizeof st);
	for(int i=1;i<=n;i++){
		int s=0;
		for(int j=0;j<m;j++)	if(a[i][j]>=mid)	s|=(1<<j);
		st[s]=i;
	}
	for(int i=(1<<m);i>=0;i--){
		for(int j=0;j<m;j++)	if(st[i|(1<<j)])	st[i]=st[i|(1<<j)];
	}
	for(int i=0;i<(1<<m);i++){
		if(st[i]&&st[((1<<m)-1)^i]){
			res1=st[i],res2=st[((1<<m)-1)^i];	return 1;
		}
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	for(int j=0;j<m;j++)	scanf("%d",&a[i][j]);
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))	l=mid;
		else	r=mid-1;
	}
	cout<<res1<<' '<<res2;
	return 0;
}

E: We consider the front position. We can move forward only when the current person is walking forward. Otherwise, the position will either remain the same or move back. So let's think about the final position. The last position is actually to see how many people are in front of us. Then we can use the tree array to maintain how many people are in front of us. Because we move to the front, our first position is m+1.

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int d[N<<1],n,m,l[N],r[N],pos[N],len;
inline void add(int x,int v){for(x;x<=len;x+=(x&(-x))) d[x]+=v;}
inline int ask(int x){int s=0; for(;x;x-=(x&(-x))) s+=d[x]; return s;}
signed main(){
	cin>>n>>m;	len=n+m;
	iota(l+1,l+1+n,1);	iota(r+1,r+1+n,1);
	for(int i=1;i<=n;i++)	pos[i]=m+i,add(pos[i],1);
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);	l[x]=1;
		r[x]=max(r[x],ask(pos[x]));
		add(pos[x],-1);	pos[x]=m+1-i; add(pos[x],1);
	}
	for(int i=1;i<=n;i++)	r[i]=max(r[i],ask(pos[i]));
	for(int i=1;i<=n;i++)	printf("%d %d\n",l[i],r[i]);
	return 0;
}