Codeforces Round #593 (Div. 2) D 模拟题
https://codeforces.com/contest/1236/problem/D
题意:
有障碍物的一个离散地图,问能不能只右转遍历所有白块(一个白块只能走一次)
思路:
思路很简单,暴力找到单方向最远走多远就好了,可以用set维护然后lower_bound。注意分类讨论就好了。
代码:
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define PB push_back
#define ll long long
#define pii pair<int,int>
#define MEM(x,y) memset(x,y,sizeof(x))
#define bug(x) cout<<"debug "#x" is "<<x<<endl;
#define FIO ios::sync_with_stdio(false);
#define ALL(x) x.begin(),x.end()
#define LOG 20
const int inf =0x3f3f3f3f;
const int maxn =1e5+7;
const int mod = 1e9+7;
set<int> X[maxn],Y[maxn];
set<int> overX,overY;
set<pii> P;
int main(){
FIO;
int n,m,x,y,k,t;
ll ans=0;
cin>>n>>m>>k;
for(int i=0;i<k;i++){
cin>>x>>y;
X[x].insert(y);
Y[y].insert(x);
P.insert({x,y});
}
pii S={1,1};
int flag=0;
while(true){
pii ns=S;
int x=S.X,y=S.Y;
if(flag==0){
auto it=X[x].upper_bound(S.Y);
if(it==X[x].end()){
t=m;
}
else t=*it-1;
auto it2=overY.upper_bound(S.Y);
if(it2==overY.end()){
t=min(t,m);
}
else t=min(t,*it2-1);
ns.Y=t;ns.X=x+1;
ans+=(ll)ns.Y-S.Y+1;
overX.insert(S.X);
}
else if(flag==1){
auto it=Y[y].upper_bound(S.X);
if(it==Y[y].end()){
t=n;
}
else t=*it-1;
auto it2=overX.upper_bound(S.X);
if(it2==overX.end()){
t=min(t,n);
}
else t=min(t,*it2-1);
ns.X=t;ns.Y=y-1;
ans+=(ll)ns.X-S.X+1;
overY.insert(S.Y);
}
else if(flag==2){
auto it=X[x].upper_bound(S.Y);
if(it==X[x].begin()){
t=1;
}
else t=*(--it)+1;
auto it2=overY.upper_bound(S.Y);
if(it2==overY.begin()){
t=max(t,1);
}
else t=max(t,*(--it2)+1);
ns.Y=t;ns.X=x-1;
ans+=(ll)S.Y-ns.Y+1;
overX.insert(S.X);
}
else{
auto it=Y[y].upper_bound(S.X);
if(it==Y[y].begin()){
t=1;
}
else t=*(--it)+1;
auto it2=overX.upper_bound(S.X);
if(it2==overX.begin()){
t=max(t,1);
}
else t=max(t,*(--it2)+1);
ns.X=t;ns.Y=y+1;
ans+=(ll)S.X-ns.X+1;
overY.insert(S.Y);
}
if(ns==S)break;
S=ns;
if(overX.count(S.X)||overY.count(S.Y)||P.count(S))break;
flag=(flag+1)%4;
}
if(ans+k==(ll)n*m)puts("Yes");
else puts("No");
return 0;
}