Codeforces Round #593 (Div. 2) D 模拟题 考试时候居然一个符号写错了。。。哭了,写代码不要复制!! https://codeforces.com/contest/1236/problem/D 题意: 有障碍物的一个离散地图,问能不能只右转遍
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; }