[CF846D]Monitor题解

看了一眼这题所用的操作，我觉得二维树状数组珂做，然后发现如果按时间顺序把节点一个个加进去再判会TLE，但发现二分时间明显比刚刚的做法快，于是二分时间+暴力插入该时间之内的点+树状数组维护即可AC

贴个代码：

#include <cstdio>

#include <cstring>

#define ll long long

#define lowbit(x) (x&(-x))

inline ll read(){

    ll x = 0; int zf = 1; char ch = ' ';

    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

    if (ch == '-') zf = -1, ch = getchar();

    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;

}

int C[1005][1005];

int n, m, k, q;

int xi[250005], yi[250005];

ll ti[250005];

void clr(){

    memset(C, 0, sizeof(C));

}

void modify(int i, int j, int val){

    for(int x = i; x <= n; x += lowbit(x))

        for(int y = j; y <= m; y += lowbit(y))

            C[x][y] += val;

}

int getsum(int i, int j){

   int res = 0;

   for(int x = i; x > 0; x -= lowbit(x))

        for(int y = j; y > 0; y -= lowbit(y))

            res += C[x][y];

   return res;

}

inline bool judge(ll num){

    clr();

    for (int i = 1; i <= q; ++i)

        if (ti[i] <= num)

            modify(xi[i], yi[i], 1);

    for (int i = k; i <= n; ++i)

        for (int j = k; j <= m; ++j){

            int tmp1 = getsum(i, j) - getsum(i - k, j) - getsum(i, j - k) + getsum(i - k, j - k);

            if (tmp1 == k * k)

                return true;

        }

    return false;

}

int main(){

    n = read(), m = read(), k = read(), q = read();

    ll _max = 0;

    for (int i = 1; i <= q; ++i){

        xi[i] = read(), yi[i] = read(), ti[i] = read();

        if (ti[i] > _max) _max = ti[i];

    }

    ll l = 0, r = _max + 1, ans = -1;

    while (l <= r){

        ll mid = (l + r) >> 1ll;

        if (judge(mid)){

            r = mid - 1;

            ans = mid;

        }

        else

            l = mid + 1;

    }

    printf("%d", ans);

    return 0;

}

巴特西

[CF846D]Monitor题解

最新文章

热门文章