首页 > 代码库 > White Streaks

White Streaks

2024-08-11 17:19:06   218人阅读

White Streaks

Time limit: 1.0 second
Memory limit: 64 MB
The life of every unlucky person has not only black but also white streaks. The Martian Vas-Vas has a calendar in the form of an m × n table; he marks in this calendar days when he had bad luck. If Vas-Vas had bad luck in the jth day of the ith week, he paints the cell (i, j) black. Initially, all cells are white.
Let rectangles of the form 1 × l or l × 1 be called segments of life. Maximal with respect to inclusion white segments are called white streaks. Can you determine how many white streaks there were in the life of Vas-Vas?

Input

The first line contains integers m, n, and k, which are the size of the calendar and the number of unlucky days in it (1 ≤ m, n ≤ 30000; 0 ≤ k ≤ 60000). In the following k lines, unlucky days are given in the form of pairs (xi, yi), where xi is the number of the week to which the unlucky day belongs and yi is the number of the day within this week (1 ≤ xi ≤ m; 1 ≤ yi ≤ n). Every unlucky day is given in the input only once.

Output

Output the number of white streaks in the life of Vas-Vas.

Samples

inputoutput
3 5 41 11 52 23 3
8
5 1 22 13 1
2

 

分析：模拟，注意周围只有自己一个白格子时算一个；

　　　参照http://www.cnblogs.com/shangyu/archive/2013/10/01/3348500.html；

代码：

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <hash_map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=3e4+10;const int dis[][2]={0,1,-1,0,0,-1,1,0};using namespace std;using namespace __gnu_cxx;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,now,ans;vi a[maxn],b[maxn];int main(){    int i,j;    scanf("%d%d%d",&n,&m,&k);    rep(i,1,k)    {        int x,y;        scanf("%d%d",&x,&y);        a[x].pb(y),b[y].pb(x);    }    rep(i,1,n)    {        a[i].pb(m+1);        sort(a[i].begin(),a[i].end());        now=0;        for(int x:a[i])        {            if(x-now>2)ans++;            now=x;        }    }    rep(i,1,m)    {        b[i].pb(n+1);        sort(b[i].begin(),b[i].end());        now=0;        for(int x:b[i])        {            if(x-now>2)ans++;            else if(x-now==2)            {                int y=x-1,pre=0;                for(int r:a[y])                {                    if(r>i)                    {                        if(r-pre==2)ans++;                        break;                    }                    pre=r;                }            }            now=x;        }    }    printf("%d\n",ans);    //system("Pause");    return 0;}

White Streaks


联系
我们