比赛 |
国庆欢乐赛3 |
评测结果 |
AAAAAAAAAAAAAAA |
题目名称 |
Following Directions |
最终得分 |
100 |
用户昵称 |
梦那边的美好TE |
运行时间 |
0.773 s |
代码语言 |
C++ |
内存使用 |
19.42 MiB |
提交时间 |
2025-10-05 09:18:46 |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
const int N=2010;
int f[N*N],n,siz[N*N],q,c[N*N];
char s[N][N];
long long sum;
int id(int x,int y){
return (x-1)*(n+1)+y;
}
int main(){
freopen("zunxun.in","r",stdin);
freopen("zunxun.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=n;j++){
if(s[i][j]=='R')f[id(i,j)]=id(i,j+1);
else f[id(i,j)]=id(i+1,j);
}
scanf("%d",&c[id(i,n+1)]);
}
for(int i=1;i<=n;i++){
scanf("%d",&c[id(n+1,i)]);
}
for(int i=n;i>=1;i--){
for(int j=n;j>=1;j--){
int x=id(i,j);
c[x]=c[f[x]];
sum+=c[x];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x=id(i,j);
siz[x]++;
siz[f[x]]+=siz[x];
}
}
printf("%lld\n",sum);
scanf("%d",&q);
int i,j,x,y,v1,v2;
while(q--){
scanf("%d %d",&i,&j);
x=id(i,j);
y=x;while(f[y])y=f[y];v1=c[y];
y=f[x];while(f[y])siz[y]-=siz[x],y=f[y];
if(s[i][j]=='D'){
f[x]=id(i,j+1);
s[i][j]='R';
}else{
f[x]=id(i+1,j);
s[i][j]='D';
}
y=f[x];while(f[y])siz[y]+=siz[x],y=f[y];v2=c[y];
sum+=1ll*(v2-v1)*siz[x];
printf("%lld\n",sum);
}
return 0;
}