URAL/1628

来自"NOCOW"

啊，STL水过。。。

嗯，第400题，纪念下。。。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
int n,m,k,ans;
vector<int> x[30001],y[30001];
vector<int>::iterator t;
int main()
{
    int i,j,a,b;
    scanf("%d%d%d",&n,&m,&k);
    for (ans=0,i=1;i<=n;++i)
    {
        y[i].push_back(0);
        y[i].push_back(m+1);
    }
    for (i=1;i<=m;++i)
    {
        x[i].push_back(0);
        x[i].push_back(n+1);
    }
    for (i=1;i<=k;++i)
    {
        scanf("%d%d",&a,&b);
        y[a].push_back(b);
        x[b].push_back(a);
    }
    for (i=1;i<=n;++i)  sort(y[i].begin(),y[i].end());
    for (i=1;i<=m;++i)  sort(x[i].begin(),x[i].end());
    for (i=1;i<=n;++i)
        for (j=1;j<y[i].size();++j)
            if (y[i][j]-y[i][j-1] > 2)
                ++ans;
            else if (y[i][j]-y[i][j-1] == 2)
            {
                a=y[i][j]-1;
                t=upper_bound(x[a].begin(),x[a].end(),i);
                b=*t;
                if (b-*(--t) == 2)  ++ans;
            }
    for (i=1;i<=m;++i)
        for (j=1;j<x[i].size();++j)
            if (x[i][j]-x[i][j-1] > 2)
                ++ans;
    printf("%d\n",ans);
    return 0;
}
//by zzy