# Codeforces SWERC 2021-2022 – Online Mirror 部分简要题解(Codeforces swerc 2021-2022 – brief explanation of online mirror)-其他

## Codeforces SWERC 2021-2022 – Online Mirror 部分简要题解(Codeforces swerc 2021-2022 – brief explanation of online mirror)

### A. Organizing SWERC

priority_queue<int> a[20];
int n;

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
cin>>n;
rep(i,1,n) {
int x,y;
cin>>x>>y;
a[y].push(x);
}
int ans=0;
rep(i,1,10) {
if (a[i].empty()) {
ans=-1;
break;
} else {
int x=a[i].top();
ans+=x;
}
}
if (ans<0) cout<<"MOREPROBLEMS"<<endl;
else cout<<ans<<endl;
rep(i,1,10) {
while (!a[i].empty()) a[i].pop();
}
}
}


### C. European Trip

namespace My_Math{
#define N 100000

int fac[N+100],invfac[N+100];

int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}

int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}

void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;

struct Matrix{
int n,m;
int x[N][N];
void out() {
rep(i,1,n) {
rep(j,1,m) cout<<x[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
};

Matrix operator *(Matrix &a,Matrix &b) {
Matrix c;
c.n=a.n;c.m=b.m;
rep(i,1,c.n) rep(j,1,c.m) c.x[i][j]=0;
rep(i,1,a.n) rep(j,1,a.m) rep(k,1,b.m)
return c;
}

Matrix qpow(Matrix x,int y) {
Matrix ans;ans.n=ans.m=x.n;
rep(i,1,ans.n) rep(j,1,ans.n) ans.x[i][j]=(i==j);
while (y) {
if (y&1) ans=ans*x;
x=x*x;y>>=1;
}
return ans;
}

Matrix a,b,d,A,tr;
int n,m,k;

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m>>k;
a.n=a.m=b.n=b.m=n;
A.n=n;A.m=n*2;tr.n=n*2;tr.m=n*2;
rep(i,1,m) {
int u,v;
cin>>u>>v;
a.x[u][v]++;a.x[v][u]++;
d.x[u][u]++;d.x[v][v]++;
}
if (k==1) {
int ans=0;
cout<<ans<<endl;
return 0;
}
Matrix s1=a,s2=qpow(a,2);

rep(i,1,n) rep(j,1,n) s2.x[i][j]=dec(s2.x[i][j],d.x[i][j]);
//s2.out();
rep(i,1,n) rep(j,1,n) A.x[i][j]=s2.x[i][j];
rep(i,1,n) rep(j,1,n) A.x[i][j+n]=s1.x[i][j];
rep(i,1,n) rep(j,1,n) tr.x[i][j]=a.x[i][j];
rep(i,1,n) rep(j,1,n) tr.x[i+n][j]=dec((i==j),d.x[i][j]);
rep(i,1,n) rep(j,1,n) tr.x[i][j+n]=(i==j);
tr=qpow(tr,k-2);
//tr.out();
A=A*tr;
int ans=0;
cout<<ans<<endl;
return 0;
}


### D. Evolution of Weasels

char sta[N];

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
string u,v;
cin>>u>>v;
reverse(v.begin(),v.end());
string s=u+v;
int cnt=0;
string t="";
int n=s.size();
rep(i,0,n-1) {
if (s[i]=='B') cnt++;
else t=t+s[i];
}
if (cnt&1) cout<<"NO";
else {
n=t.size();
if (n&1) cout<<"NO";
else {
int tp=0;
rep(i,0,n-1) {
if ((!tp)||(sta[tp]!=s[i])) sta[++tp]=s[i];
else tp--;
}
if (tp==0) cout<<"YES";
else cout<<"NO";
}
}
cout<<endl;
}
return 0;
}


### F. Antennas

int n,a[N],b[N],c[N],seg[N<<2][2];
bool vis[N];
queue<pii> q;

int max0(int x,int y) {if (b[x]>b[y]) return x;else return y;}
int max1(int x,int y) {if (c[x]<c[y]) return x;else return y;}

void modify(int id,int l,int r,int p,int op) {
if (l==r) {
seg[id][op]=0;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(id<<1,l,mid,p,op);
else modify(id<<1|1,mid+1,r,p,op);
seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int query0(int id,int l,int r,int ql,int qr) {
if ((l>=ql)&&(r<=qr)) return seg[id][0];
int mid=(l+r)>>1,ans=0;
if (ql<=mid) ans=max0(ans,query0(id<<1,l,mid,ql,qr));
if (qr>mid) ans=max0(ans,query0(id<<1|1,mid+1,r,ql,qr));
return ans;
}

int query1(int id,int l,int r,int ql,int qr) {
if ((l>=ql)&&(r<=qr)) return seg[id][1];
int mid=(l+r)>>1,ans=0;
if (ql<=mid) ans=max1(ans,query1(id<<1,l,mid,ql,qr));
if (qr>mid) ans=max1(ans,query1(id<<1|1,mid+1,r,ql,qr));
return ans;
}

void build(int id,int l,int r) {
if (l==r) {
seg[id][0]=seg[id][1]=l;
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid); build(id<<1|1,mid+1,r);
seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int main() {
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
int st,ed;
cin>>n>>st>>ed;
rep(i,1,n) cin>>a[i];
rep(i,1,n) {
b[i]=i+a[i];
c[i]=i-a[i];
}
b[0]=0;c[0]=n*3;
build(1,1,n);
q.push(mkp(st,0));
while (!q.empty()) {
pii now=q.front();q.pop();
int u=now.fir;
if (u==ed) {
cout<<now.sec<<endl;
break;
}
if (vis[u]) continue;vis[u]=1;
int l=max(1,u-a[u]),r=min(n,u+a[u]);
while (1) {
int v=query0(1,1,n,l,u);
if (b[v]<u) break;
q.push(mkp(v,now.sec+1));
modify(1,1,n,v,0);
}
while (1) {
int v=query1(1,1,n,u,r);
if (c[v]>u) break;
q.push(mkp(v,now.sec+1));
modify(1,1,n,v,1);
}
}
while (!q.empty()) q.pop();
rep(i,1,n) vis[i]=0;
}
return 0;
}


### H. Boundary

set<int> s;
void solve(int n,int m) {
if ((n<0)||(m<0)) return;
int d=__gcd(n,m);
for (int i=1;i*i<=d;i++) {
if (d%i==0) {s.insert(i);s.insert(d/i);}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
int n,m;
cin>>n>>m;
s.clear();
solve(n-1,m-1);
solve(n,m-2);
solve(n-2,m);
s.insert(2);
int siz=s.size();
cout<<siz<<" ";
set<int>::iterator it;
for (it=s.begin();it!=s.end();it++) cout<<(*it)<<" ";
cout<<endl;
}
}


### I. Ice Cream Shop

int n,m,p[N],b[N];
map<ll,ll> a;

int main() {
cin>>n>>m;
rep(i,1,n) cin>>p[i];
rep(i,1,m) cin>>b[i];
sort(b+1,b+1+m);
b[m+1]=2e9;b[0]=-200;
rep(i,1,n) {
int np=(i-1)*100;
int pos=lower_bound(b,b+m+2,np)-b;
int r=pos,l=pos-1;
ll d=min(b[r]-np,np-b[l]);
a[np-d]+=p[i];a[np+d]-=p[i];
}
ll ans=0,now=0;
for (auto &x:a) {
now+=x.sec;
ans=max(ans,now);
}
cout<<ans<<endl;
return 0;
}


### L. Il Derby della Madonnina

int n,a[N],b[N],t[N],tot;
ll v,f[N];
pair<ll,ll> p[N];

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>v;
rep(i,1,n) cin>>t[i];
rep(i,1,n) cin>>a[i];
rep(i,1,n) p[i]=mkp(v*t[i]-a[i],v*t[i]+a[i]);
sort(p+1,p+n+1);
rep(i,1,n) {
ll tmp=p[i].sec;
if ((p[i].fir<0)||(p[i].sec<0)) continue;
if (tmp>=f[tot]) f[++tot]=tmp;
else {
int p=upper_bound(f+1,f+1+tot,tmp)-f;
f[p]=tmp;
}
}
cout<<tot;
return 0;
}


### M. Bottle Arrangements

int n,m;

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
cin>>n>>m;
int mx1=0,mx2=0;
rep(i,1,m) {
int r,w;
cin>>r>>w;
mx1=max(r,mx1);
mx2=max(w,mx2);
}
if (mx1+mx2>n) cout<<"IMPOSSIBLE";
else {
mx2=n-mx1;
rep(i,1,mx1) cout<<"R";
rep(i,1,mx2) cout<<"W";
}
cout<<endl;
}
}


### N. Drone Photo

1---2       1---3
|   |       |   |
|   |       |   |
3---4       2---4


1---4       1---3
|   |       |   |
|   |       |   |
3---2       4---2


int n,a[N][N],r[N][N],c[N][N],row[N],col[N];
pii pos[N*N];

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
rep(i,1,n) rep(j,1,n) {
cin>>a[i][j];
pos[a[i][j]]=mkp(i,j);
}
rep(x,1,n*n) {
int i=pos[x].fir,j=pos[x].sec;
r[i][j]=row[i];
c[i][j]=col[j];
row[i]++;col[j]++;
}
ll ans=0;
rep(i,1,n) rep(j,1,n) ans+=(n-1-r[i][j])*c[i][j]+r[i][j]*(n-1-c[i][j]);
cout<<ans/2<<endl;
return 0;
}


### O. Circular Maze

int n,a[21][400],b[400],c[21][400];
int vis[21][400];
string s;

void dfs(int r,int d) {
if (vis[r][d]) return;
vis[r][d]=1;
if (r==20) return;
int dl=0,dr=360;
if (b[r]>1) {
dl=d;dr=(d+1)%360;
while (!c[r][dl]) dl=(dl-1+360)%360;
while (!c[r][dr]) dr=(dr+1)%360;
}
while (dl!=dr) {
if (!a[r+1][dl]) dfs(r+1,dl);
if ((r)&&(!a[r][dl])) dfs(r-1,dl);
if ((dr==360) && (dl==359)) break;
dl=(dl+1)%360;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
rep(i,0,20) {
b[i]=0;
rep(j,0,359) c[i][j]=a[i][j]=vis[i][j]=0;
}
cin>>n;
rep(i,1,n) {
cin>>s;
if (s[0]=='C') {
int r,d1,d2;
cin>>r>>d1>>d2;
while (d1!=d2) {
a[r][d1]=1;
d1=(d1+1)%360;
}
} else {
int r1,r2,d;
cin>>r1>>r2>>d;
while (r1<r2) {
c[r1][d]=1;
b[r1]++;
r1++;
}
}
}
dfs(0,0);
int ok=0;
rep(i,0,359) ok|=vis[20][i];
if (ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}

————————

### A. Organizing SWERC

Check in question

priority_queue<int> a[20];
int n;

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
cin>>n;
rep(i,1,n) {
int x,y;
cin>>x>>y;
a[y].push(x);
}
int ans=0;
rep(i,1,10) {
if (a[i].empty()) {
ans=-1;
break;
} else {
int x=a[i].top();
ans+=x;
}
}
if (ans<0) cout<<"MOREPROBLEMS"<<endl;
else cout<<ans<<endl;
rep(i,1,10) {
while (!a[i].empty()) a[i].pop();
}
}
}


Coo

### C. European Trip

If the adjacency matrix of the graph is \ (a \), the path with length \ (K \) from \ (I \) to \ (J \) has \ (a ^ k)_ {ij} \), the number of paths with the same starting and ending points is \ (\ mathrm {tr} (a ^ k) \)

Consider adding special trip restrictions The matrix multiplication is still considered. Assuming that the matrix when the path length is \ (K \) is \ (f_k \), there is a transfer formula

Where \ (D \) represents the degree matrix and \ (I \) represents the identity matrix The transfer formula is written in the form of block matrix multiplication

Then the power can be obtained directly and quickly

namespace My_Math{
#define N 100000

int fac[N+100],invfac[N+100];

int add(int x,int y) {return x+y>=maxd?x+y-maxd:x+y;}
int dec(int x,int y) {return x<y?x-y+maxd:x-y;}
int mul(int x,int y) {return 1ll*x*y%maxd;}
ll qpow(ll x,int y)
{
ll ans=1;
while (y)
{
if (y&1) ans=mul(ans,x);
x=mul(x,x);y>>=1;
}
return ans;
}
int getinv(int x) {return qpow(x,maxd-2);}

int C(int n,int m)
{
if ((n<m) || (n<0) || (m<0)) return 0;
return mul(mul(fac[n],invfac[m]),invfac[n-m]);
}

void math_init()
{
fac[0]=invfac[0]=1;
rep(i,1,N) fac[i]=mul(fac[i-1],i);
invfac[N]=getinv(fac[N]);
per(i,N-1,1) invfac[i]=mul(invfac[i+1],i+1);
}
#undef N
}
using namespace My_Math;

struct Matrix{
int n,m;
int x[N][N];
void out() {
rep(i,1,n) {
rep(j,1,m) cout<<x[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
};

Matrix operator *(Matrix &a,Matrix &b) {
Matrix c;
c.n=a.n;c.m=b.m;
rep(i,1,c.n) rep(j,1,c.m) c.x[i][j]=0;
rep(i,1,a.n) rep(j,1,a.m) rep(k,1,b.m)
return c;
}

Matrix qpow(Matrix x,int y) {
Matrix ans;ans.n=ans.m=x.n;
rep(i,1,ans.n) rep(j,1,ans.n) ans.x[i][j]=(i==j);
while (y) {
if (y&1) ans=ans*x;
x=x*x;y>>=1;
}
return ans;
}

Matrix a,b,d,A,tr;
int n,m,k;

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m>>k;
a.n=a.m=b.n=b.m=n;
A.n=n;A.m=n*2;tr.n=n*2;tr.m=n*2;
rep(i,1,m) {
int u,v;
cin>>u>>v;
a.x[u][v]++;a.x[v][u]++;
d.x[u][u]++;d.x[v][v]++;
}
if (k==1) {
int ans=0;
cout<<ans<<endl;
return 0;
}
Matrix s1=a,s2=qpow(a,2);

rep(i,1,n) rep(j,1,n) s2.x[i][j]=dec(s2.x[i][j],d.x[i][j]);
//s2.out();
rep(i,1,n) rep(j,1,n) A.x[i][j]=s2.x[i][j];
rep(i,1,n) rep(j,1,n) A.x[i][j+n]=s1.x[i][j];
rep(i,1,n) rep(j,1,n) tr.x[i][j]=a.x[i][j];
rep(i,1,n) rep(j,1,n) tr.x[i+n][j]=dec((i==j),d.x[i][j]);
rep(i,1,n) rep(j,1,n) tr.x[i][j+n]=(i==j);
tr=qpow(tr,k-2);
//tr.out();
A=A*tr;
int ans=0;
cout<<ans<<endl;
return 0;
}


### D. Evolution of Weasels

Provide a more strange approach?

Consider a group \ (g \) containing a, B, C and unit element E, where the operation of the elements satisfies \ (AA = BB = CC = ABAB = bcbc = e \) According to the first three items, the inverse of \ (a, B, C \) is itself There are also \ (AB = (AB) ^ {- 1} = B ^ {- 1} a ^ {- 1} = BA \), similarly \ (BC = CB \)

Or notice ba – & gt; AA[BA]BB-> A[ABAB]B-> AB.

Therefore, the position of B in the string is insignificant and can be moved at will But the relative relationship between a and C cannot be changed Consider that \ (U = V \) is equivalent to \ (UV ^ {- 1} = e \) Therefore, we can first calculate \ (UV ^ {- 1} \), remove all B, and then eliminate a or C in pairs to judge whether an empty string can be obtained at last

char sta[N];

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
string u,v;
cin>>u>>v;
reverse(v.begin(),v.end());
string s=u+v;
int cnt=0;
string t="";
int n=s.size();
rep(i,0,n-1) {
if (s[i]=='B') cnt++;
else t=t+s[i];
}
if (cnt&1) cout<<"NO";
else {
n=t.size();
if (n&1) cout<<"NO";
else {
int tp=0;
rep(i,0,n-1) {
if ((!tp)||(sta[tp]!=s[i])) sta[++tp]=s[i];
else tp--;
}
if (tp==0) cout<<"YES";
else cout<<"NO";
}
}
cout<<endl;
}
return 0;
}


Coo

### F. Antennas

First remove the absolute value, and \ (I \) can only connect edges to the points in \ ([i-p_i, I + p_i] \), so the limit of \ (p_i \) can be discarded

First, only consider the case of \ (I & gt; J \) Note that the edge weight of each edge is 1, so in the process of DIJ, each point is relaxed exactly once Therefore, we can find the largest point of \ (j + p_j \) that has not been relaxed among all points \ (J \) that meet \ (I \ Leq j + p_j \), relax it with point \ (I \), and delete it from the scope of investigation It is not necessary to use the relaxation tree to find and delete all the segments that have not been found

For the case of \ (I & lt; J \), just open another segment tree for maintenance as above

int n,a[N],b[N],c[N],seg[N<<2][2];
bool vis[N];
queue<pii> q;

int max0(int x,int y) {if (b[x]>b[y]) return x;else return y;}
int max1(int x,int y) {if (c[x]<c[y]) return x;else return y;}

void modify(int id,int l,int r,int p,int op) {
if (l==r) {
seg[id][op]=0;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(id<<1,l,mid,p,op);
else modify(id<<1|1,mid+1,r,p,op);
seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int query0(int id,int l,int r,int ql,int qr) {
if ((l>=ql)&&(r<=qr)) return seg[id][0];
int mid=(l+r)>>1,ans=0;
if (ql<=mid) ans=max0(ans,query0(id<<1,l,mid,ql,qr));
if (qr>mid) ans=max0(ans,query0(id<<1|1,mid+1,r,ql,qr));
return ans;
}

int query1(int id,int l,int r,int ql,int qr) {
if ((l>=ql)&&(r<=qr)) return seg[id][1];
int mid=(l+r)>>1,ans=0;
if (ql<=mid) ans=max1(ans,query1(id<<1,l,mid,ql,qr));
if (qr>mid) ans=max1(ans,query1(id<<1|1,mid+1,r,ql,qr));
return ans;
}

void build(int id,int l,int r) {
if (l==r) {
seg[id][0]=seg[id][1]=l;
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid); build(id<<1|1,mid+1,r);
seg[id][0]=max0(seg[id<<1][0],seg[id<<1|1][0]);
seg[id][1]=max1(seg[id<<1][1],seg[id<<1|1][1]);
}

int main() {
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
int st,ed;
cin>>n>>st>>ed;
rep(i,1,n) cin>>a[i];
rep(i,1,n) {
b[i]=i+a[i];
c[i]=i-a[i];
}
b[0]=0;c[0]=n*3;
build(1,1,n);
q.push(mkp(st,0));
while (!q.empty()) {
pii now=q.front();q.pop();
int u=now.fir;
if (u==ed) {
cout<<now.sec<<endl;
break;
}
if (vis[u]) continue;vis[u]=1;
int l=max(1,u-a[u]),r=min(n,u+a[u]);
while (1) {
int v=query0(1,1,n,l,u);
if (b[v]<u) break;
q.push(mkp(v,now.sec+1));
modify(1,1,n,v,0);
}
while (1) {
int v=query1(1,1,n,u,r);
if (c[v]>u) break;
q.push(mkp(v,now.sec+1));
modify(1,1,n,v,1);
}
}
while (!q.empty()) q.pop();
rep(i,1,n) vis[i]=0;
}
return 0;
}


Coo

### H. Boundary

Considering the case of equal length and width, it is not difficult to find that there are only \ ((n-1, m-1), (n, m-2), (n-2, m) \)

Considering the case of unequal length and width, one of the two groups of numbers \ (n, n-2 \) and \ (m, m-2 \) must exist at the same time, so only 2 may be legal

set<int> s;
void solve(int n,int m) {
if ((n<0)||(m<0)) return;
int d=__gcd(n,m);
for (int i=1;i*i<=d;i++) {
if (d%i==0) {s.insert(i);s.insert(d/i);}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
int n,m;
cin>>n>>m;
s.clear();
solve(n-1,m-1);
solve(n,m-2);
solve(n-2,m);
s.insert(2);
int siz=s.size();
cout<<siz<<" ";
set<int>::iterator it;
for (it=s.begin();it!=s.end();it++) cout<<(*it)<<" ";
cout<<endl;
}
}


### I. Ice Cream Shop

For the \ (I \) th hut Assuming that the distance between the nearest seller and it is \ (d_i \), only when the new store is located in \ ((y_i-d_i, y_i + d_i) \), can we get the benefit of \ (p_i \) (\ (y_i \) is the location of HUT) Direct difference statistics is enough

int n,m,p[N],b[N];
map<ll,ll> a;

int main() {
cin>>n>>m;
rep(i,1,n) cin>>p[i];
rep(i,1,m) cin>>b[i];
sort(b+1,b+1+m);
b[m+1]=2e9;b[0]=-200;
rep(i,1,n) {
int np=(i-1)*100;
int pos=lower_bound(b,b+m+2,np)-b;
int r=pos,l=pos-1;
ll d=min(b[r]-np,np-b[l]);
a[np-d]+=p[i];a[np+d]-=p[i];
}
ll ans=0,now=0;
for (auto &x:a) {
now+=x.sec;
ans=max(ans,now);
}
cout<<ans<<endl;
return 0;
}


Coo

Coo

### L. Il Derby della Madonnina

The simple DP formula is as follows

Disassemble the absolute value. When \ (a_i \ Leq a_j \), there is \ (vt_i + a_i \ GEQ vt_j + a_j \); When \ (a_i & gt; a_j \), there is \ (vt_i-a_i \ GEQ vt_j + a_j \)

Record these two equations as (1) and (2) respectively Note that when \ (a_i \ Leq a_j \), if equation (1) is satisfied, equation (2) is automatically satisfied; When \ (a_i & gt; a_j \), if equation (2) is satisfied, equation (1) will be satisfied automatically Therefore, the two dimensions of \ ((vt_i + a_i, vt_i-a_i) \) in the set composed of the last legal \ (I \) are monotonically increasing It can be processed in the way of LIS

int n,a[N],b[N],t[N],tot;
ll v,f[N];
pair<ll,ll> p[N];

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>v;
rep(i,1,n) cin>>t[i];
rep(i,1,n) cin>>a[i];
rep(i,1,n) p[i]=mkp(v*t[i]-a[i],v*t[i]+a[i]);
sort(p+1,p+n+1);
rep(i,1,n) {
ll tmp=p[i].sec;
if ((p[i].fir<0)||(p[i].sec<0)) continue;
if (tmp>=f[tot]) f[++tot]=tmp;
else {
int p=upper_bound(f+1,f+1+tot,tmp)-f;
f[p]=tmp;
}
}
cout<<tot;
return 0;
}


### M. Bottle Arrangements

If it is legal, there must be a form such as RR RWW… W’s plan

int n,m;

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
cin>>n>>m;
int mx1=0,mx2=0;
rep(i,1,m) {
int r,w;
cin>>r>>w;
mx1=max(r,mx1);
mx2=max(w,mx2);
}
if (mx1+mx2>n) cout<<"IMPOSSIBLE";
else {
mx2=n-mx1;
rep(i,1,mx1) cout<<"R";
rep(i,1,mx2) cout<<"W";
}
cout<<endl;
}
}


### N. Drone Photo

Consider the following legal circumstances

1---2       1---3
|   |       |   |
|   |       |   |
3---4       2---4


Notice that for all legal situations, there must be exactly two positions So that its size is in the middle of the triplet composed of two numbers adjacent to it in its own and legal case

For the following illegal situations

1---4       1---3
|   |       |   |
|   |       |   |
3---2       4---2


There must be no position in the above

Directly count the total number of triples in the above description. According to the analysis, it is exactly twice the answer

int n,a[N][N],r[N][N],c[N][N],row[N],col[N];
pii pos[N*N];

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
rep(i,1,n) rep(j,1,n) {
cin>>a[i][j];
pos[a[i][j]]=mkp(i,j);
}
rep(x,1,n*n) {
int i=pos[x].fir,j=pos[x].sec;
r[i][j]=row[i];
c[i][j]=col[j];
row[i]++;col[j]++;
}
ll ans=0;
rep(i,1,n) rep(j,1,n) ans+=(n-1-r[i][j])*c[i][j]+r[i][j]*(n-1-c[i][j]);
cout<<ans/2<<endl;
return 0;
}


### O. Circular Maze

Note that the number of \ ((R, \ theta) \) in the problem polar coordinates is not large in the discrete sense So you can use an array to express all the restrictions, and then use DFS from the origin See the following procedure for details

int n,a[21][400],b[400],c[21][400];
int vis[21][400];
string s;

void dfs(int r,int d) {
if (vis[r][d]) return;
vis[r][d]=1;
if (r==20) return;
int dl=0,dr=360;
if (b[r]>1) {
dl=d;dr=(d+1)%360;
while (!c[r][dl]) dl=(dl-1+360)%360;
while (!c[r][dr]) dr=(dr+1)%360;
}
while (dl!=dr) {
if (!a[r+1][dl]) dfs(r+1,dl);
if ((r)&&(!a[r][dl])) dfs(r-1,dl);
if ((dr==360) && (dl==359)) break;
dl=(dl+1)%360;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;cin>>T;
while (T--) {
rep(i,0,20) {
b[i]=0;
rep(j,0,359) c[i][j]=a[i][j]=vis[i][j]=0;
}
cin>>n;
rep(i,1,n) {
cin>>s;
if (s[0]=='C') {
int r,d1,d2;
cin>>r>>d1>>d2;
while (d1!=d2) {
a[r][d1]=1;
d1=(d1+1)%360;
}
} else {
int r1,r2,d;
cin>>r1>>r2>>d;
while (r1<r2) {
c[r1][d]=1;
b[r1]++;
r1++;
}
}
}
dfs(0,0);
int ok=0;
rep(i,0,359) ok|=vis[20][i];
if (ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}