Codeforces Round #593 (Div. 2) D 模拟题

考试时候居然一个符号写错了。。。哭了，写代码不要复制！！

https://codeforces.com/contest/1236/problem/D

题意：

有障碍物的一个离散地图，问能不能只右转遍历所有白块（一个白块只能走一次）

思路：

思路很简单，暴力找到单方向最远走多远就好了，可以用set维护然后lower_bound。注意分类讨论就好了。

代码：

#include 
using namespace std;
#define X first
#define Y second
#define PB push_back
#define ll long long
#define pii pair
#define MEM(x,y) memset(x,y,sizeof(x))
#define bug(x) cout<<"debug "#x" is "< X[maxn],Y[maxn];
set overX,overY;
set P;
int main(){
    FIO;
    int n,m,x,y,k,t;
    ll ans=0;
    cin>>n>>m>>k;
    for(int i=0;i>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;
}