Codeforces Round #593 (Div. 2)D（螺旋形模拟）

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
vector<int>po[100007],col[100007];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,k;
cin>>n>>m>>k;
int x=0,y=0;
for(int i=1;i<=k;++i){
cin>>x>>y;
po[x].push_back(y);
col[y].push_back(x);
}
long long sum=0;
int tamp=m;
x=1,y=1;
for(int i=0;i<po[1].size();++i)if(po[x][i]>1)
tamp=min(tamp,po[1][i]-1);
sum=tamp;
int a=0,b=0,c=0,d=0;//a为上边界，b为右边界，c为下边界，d为左边界
a=1;
y=tamp;//y为当前处于哪一列
while(1){
tamp=n-c;//tamp为当前行/列最远能走到的位置
for(int i=0;i<col[y].size();++i)if(col[y][i]>x)
tamp=min(tamp,col[y][i]-1);
if(tamp==x)
break;
sum+=tamp-x;
b=m-y+1;
x=tamp;//x为当前处于哪一行
tamp=d+1;
for(int i=0;i<po[x].size();++i)if(po[x][i]<y)
tamp=max(tamp,po[x][i]+1);
if(tamp==y)
break;
sum+=y-tamp;
c=n-x+1;
y=tamp;
tamp=a+1;
for(int i=0;i<col[y].size();++i)if(col[y][i]<x)
tamp=max(tamp,col[y][i]+1);
if(tamp==x)
break;
sum+=x-tamp;
d=y;
x=tamp;
tamp=m-b;
for(int i=0;i<po[x].size();++i)if(po[x][i]>y)
tamp=min(tamp,po[x][i]-1);
if(tamp==y)
break;
sum+=tamp-y;
a=x;
y=tamp;
}
if(sum==1ll*n*m-1ll*k)
cout<<"Yes";
else
cout<<"No";
return 0;
}

巴特西

Codeforces Round #593 (Div. 2)D（螺旋形模拟）

最新文章

热门文章