http://www.codechef.com/MAY14/problems/CHEFBM

对于每一行,利用map,先判断是否为不降序列,再用结尾减开头就行。

/*0.37s,5.5MB*/

const int mx = 100005;

vector<int> v[mx];
map<int, int> mp;
miter it, tmp;
int m;

int f(int i)
{
    int si = v[i].size(), j, beg = 0;
    if (si)
    {
        mp.clear();
        For(j, si) ++mp[v[i][j]];
        loop(mp)
        {
            if (it->x == 1) beg = it->y;
            if (it->x == m) return m - 1 - beg + it->y;
            else if (tmp = it, it->x + 1 == (++tmp)->x) /// 判断是否相邻
         {
                if (it->y - 1 > tmp->y) return -1;
            }
            else if (it->y > 1) return -1;
        }
    }
    return m - 1 - beg;
}

int main()
{
    int n, m, p, xx, yy, i;
    SIII(n, m, p);
    while (p--) SII(xx, yy), v[xx].PB(yy);
    Forr(i, 1, n + 1) PI(f(i));
    return 0;
}

Comments

comments powered by Disqus