# Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics)

## A

The author, you [].

We need a dynamic space. You use a vector to save this matrix. Just resize it at the beginning.

Then consider making a question, and think of dividing the vertical and horizontal to calculate the distance. Open a bucket for each color, then record the horizontal and vertical coordinates of each color, traverse the coordinates from small to large, and then find the current answer linearly.

My Code
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=1e5+10;
int cnt[MAXN];
vector<int> c[MAXN],x[MAXN],y[MAXN];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;cin>>n>>m;
rep(i,1,n){
c[i].resize(m+5);
rep(j,1,m) cin>>c[i][j];
}
int ans=0,tot=0;
rep(i,1,n) rep(j,1,m){
int cur;
if(cnt[c[i][j]]) cur=cnt[c[i][j]];
else cnt[c[i][j]]=++tot,cur=tot;
x[cur].pb(i);y[cur].pb(j);
}
rep(i,1,tot){
sort(x[i].begin(),x[i].end());
sort(y[i].begin(),y[i].end());
int num=0,lst=x[i][0],fns=0;
for(int s:x[i]) ans+=(fns=num*(s-lst)+fns),lst=s,num++;
num=0,lst=y[i][0],fns=0;
for(int s:y[i]) ans+=(fns=num*(s-lst)+fns),lst=s,num++;
}cout<<ans<<'\n';
return 0;
}



## B

Consider the following:

$\lfloor\dfrac{x}{y}\rfloor=z\Leftrightarrow x=yz+k(k<y)$

So consider enumerating a \ (Z \) that is not in the \ (a \) array to see if \ (x,y \) can represent it. In this way, for each \ (Z \), we only need to enumerate \ (\ dfrac{c}{z} \) intervals, and then use prefix and preprocessing to \ (O(1) \) judge whether there are numbers in an interval.

My Code
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=2e6+10;
int sum[MAXN];
void solve(){
int n,c,a;cin>>n>>c;
rep(i,1,n) cin>>a,sum[a]++;
rep(i,1,c*2) sum[i]+=sum[i-1];
bool ok=1;
rep(z,1,c){
if(sum[z]-sum[z-1]) continue;
for(int y=1;y*z<=c;y++){
//			cerr<<sum[y]<<' '<<sum[y-1]<<' '<<sum[y*z+y-1]<<' '<<sum[y*z-1]<<' '<<y<<' '<<z<<'\n';
//			cerr<<y*z+y-1<<' '<<y*z-1<<'\n';
if((sum[y]-sum[y-1])>0&&(sum[y*z+y-1]-sum[y*z-1])>0){
ok=0;
}
}
}
rep(i,1,c*2) sum[i]=0;
if(ok) cout<<"Yes\n";
else cout<<"No\n";
}
signed main()
{
ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
int T;for(cin>>T;T--;)
solve();
return 0;
}


# CRT, first [], rebuild pretest!

Note that this question has a very weak pretest!!!

Consider the routine of counting questions for dictionary order comparison, and consider enumerating which position \ (s_i < t_i \), and then the previous positions are equal, and the subsequent positions are filled in casually.

Then consider using a tree array to maintain the enumeration to the position of \ (I \). Remove the numbers that have been filled in the front and are equal to \ (t_i \), and how much is left for each number. Then, for enumerating to position \ (I \), there are still \ (n-i+1 \) numbers left.

Then we force \ (I \) to fill in less than \ (t_i \), so the position of the remaining \ (n-i \) can be filled in at will. That is, if we set the current number of each number to be \ (cnt_i \), the sum of all numbers to be \ (tot \), and the sum of numbers smaller than \ (t_i \) to be \ (tmp \), then the answer to the current position will be added:

\begin{aligned}\sum_{c<t_i}\dfrac{tot!}{\prod cnt_i!}\times cnt_c &=\dfrac{tot!}{\prod cnt_i!}\times tmp\end{aligned}

Then you can maintain \ (\ prod cnt_i! \) with a variable.

Note that finally, it is necessary to judge whether \ (s \) can be the prefix of \ (t \). When enumerating, just mark it to judge whether it is the prefix.

My Code
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
using namespace std;
const int MAXN=2e5+10;
const int MOD=998244353;
int ksm(int a,int p){
int ret=1;while(p){
if(p&1) ret=ret*a%MOD;
a=a*a%MOD; p>>=1;
}return ret;
}
int inv(int x){return ksm(x,MOD-2);}
struct Tree{int l,r,cnt;}tr[MAXN<<2];
int fac[MAXN];
#define ls i<<1
#define rs i<<1|1
void build(int i,int l,int r){
tr[i].l=l;tr[i].r=r;tr[i].cnt=0;
if(l==r) return;int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
void pushup(int i){
tr[i].cnt=tr[ls].cnt+tr[rs].cnt;
}
void upd(int i,int x,int v){
if(tr[i].l==tr[i].r){tr[i].cnt+=v;return;}
int mid=tr[i].l+tr[i].r>>1;
if(x<=mid) upd(ls,x,v);else upd(rs,x,v);
pushup(i);
}
int qcnt(int i,int l,int r){
if(l>r) return 0;
if(tr[i].l==l&&tr[i].r==r) return tr[i].cnt;
int mid=tr[i].l+tr[i].r>>1;
if(r<=mid) return qcnt(ls,l,r);
else if(l>mid) return qcnt(rs,l,r);
else return qcnt(ls,l,mid)+qcnt(rs,mid+1,r);
}
int s[MAXN],t[MAXN];
int cs[MAXN];
signed main()
{
ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
fac[0]=1;rep(i,1,MAXN-10) fac[i]=fac[i-1]*i%MOD;
int n,m;cin>>n>>m;build(1,1,MAXN-10);
rep(i,1,n) cin>>s[i],cs[s[i]]++,upd(1,s[i],1);
rep(i,1,m) cin>>t[i];
int all=1;
rep(i,1,MAXN-10) all=all*fac[cs[i]]%MOD;
int ans=0,ok=1;
rep(i,1,min(n,m)){
int tmp=qcnt(1,1,t[i]-1);
//		cerr<<tmp<<'\n';
if(tmp){
int rem=n-i;
ans+=fac[rem]*inv(all)%MOD*tmp%MOD;
ans%=MOD;
}
if(!cs[t[i]]){ok=0;break;}
else all=all*inv(cs[t[i]])%MOD,cs[t[i]]--,upd(1,t[i],-1);
//		rep(j,1,3) cerr<<qcnt(1,j,j)<<' ';cerr<<'\n';
}
if(n>=m) ok=0;
cout<<(ans+ok)%MOD<<'\n';
return 0;
}/*
3 6
10 7 8
8 7 6 10 5 4
*/


Added by ryanh_106 on Mon, 07 Mar 2022 07:28:47 +0200