WA on test16,扫描线做法求救
查看原帖
WA on test16,扫描线做法求救
507348
__vector__楼主2023/4/15 16:46


本蒟蒻没啥别的,帮我调出来给 33 个关注。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
const int maxn = 505;
int n, m, k;
struct Node
{
    int x, y;
    // 横坐标,纵坐标
} node[maxn];
ll lsh[maxn * 2];
int lshtop;
struct Line
{
    ll x, y1, y2, mark;
    // y1 是这条竖线的上端点,y2 是下端点
} line[maxn * 2];
int linetop;
ll sgtcnt[maxn << 3], L[maxn << 3], R[maxn << 3], maxup[maxn << 3], mindw[maxn << 3];
// maxup 是最高的没覆盖点,min 是最低的没覆盖,注意这个是离散化之后的值
void build(int pos, int l, int r)
{
    sgtcnt[pos]=0;
    L[pos] = l;
    R[pos] = r;
    maxup[pos] = r;
    mindw[pos] = l;
    if (l == r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    build(pos << 1, l, mid);
    build(pos << 1 | 1, mid + 1, r);
}
void pushup(int now)
{
    if (sgtcnt[now])
    {
        maxup[now] = -5e9;
        mindw[now] = 5e9;
    }
    else
    {
        if(L[now]!=R[now])
        {
            maxup[now] = max(maxup[now << 1], maxup[now << 1 | 1]);
            mindw[now] = min(mindw[now << 1], mindw[now << 1 | 1]);
        }
        else
        {
            maxup[now]=mindw[now]=L[now];
        }
    }
}
void change(int now, int l, int r, int val)
{
    if (l <= L[now] && R[now] <= r)
    {
        sgtcnt[now] += val;
        pushup(now);
        return;
    }
    if (L[now] > r || R[now] < l)
        return;
    int mid = (L[now] + R[now]) >> 1;
    if (mid >= l)
        change(now << 1, l, r, val);
    if (mid < r)
        change(now << 1 | 1, l, r, val);
    pushup(now);
}
bool check(ll time)
{
    lshtop = 0, linetop = 0;
    FOR(i, 1, k)
    {
        lsh[++lshtop] = min(1ll*n, node[i].y + time);
        lsh[++lshtop] = max(1ll, node[i].y - time);
    }
    sort(lsh + 1, lsh + lshtop + 1);
    lshtop = unique(lsh + 1, lsh + lshtop + 1) - lsh - 1;
    FOR(i, 1, k)
    {
        int nwy1 = lower_bound(lsh + 1, lsh + lshtop + 1, min(1ll*n, node[i].y + time)) - lsh;
        int nwy2 = lower_bound(lsh + 1, lsh + lshtop + 1, max(1ll, node[i].y - time)) - lsh;
        line[++linetop] = {max(1ll, node[i].x - time), nwy1, nwy2, 1};
        line[++linetop] = {min(1ll*m, node[i].x + time)+1, nwy1, nwy2, -1};
    }
    sort(line + 1, line + linetop + 1, [&](Line &a, Line &b)
         {  if(a.x!=b.x)
                return a.x < b.x; 
            else
                return a.mark>b.mark;
            });
    build(1, 1, lshtop);
    ll maxupf = -5e9, mindwf = 5e9, maxrigf = -5e9, minleff = 5e9;
    if (line[1].x > 1)
    {
        maxupf = n;
        mindwf = 1;
        minleff = 1;
        maxrigf = 1;
 //       puts("Updated\n");
    }
    FOR(i, 1, linetop)
    {
        if(line[i].x>m)break;
        change(1, line[i].y2, line[i].y1, line[i].mark);

     //   printf("i = %d\n",i);
     //   printf("line[%d].x = %d line[%d].y1 = %d line[%d].y2 = %d mark = %d\n", i, line[i].x,i,line[i].y1 ,i,line[i].y2,line[i].mark);
        if (line[i].x != line[i + 1].x)
        {
            
            if (mindw[1] != 5e9)
            {
                maxupf = max(maxupf, lsh[maxup[1]]);
                mindwf = min(mindwf, lsh[mindw[1]]);
           //     printf("up = %lld dw = %lld\n",lsh[maxup[1]],lsh[mindw[1]]);
                maxrigf = max(maxrigf, line[i].x);
                minleff = min(minleff, line[i].x);
            }
        }
    }
    if (line[linetop].x < m)
    {
        maxupf = n;
        mindwf = 1;
        maxrigf = m;
        minleff = min(minleff, 1ll * m);
      //  puts("Updated2");
    }
 //   printf("maxup = %lld mindw = %lld maxrig = %lld minlef = %lld\n", maxupf, mindwf, maxrigf, minleff);
    return ((maxupf - mindwf + 1 <= time * 2 + 1) && (maxrigf - minleff + 1 <= time * 2 + 1));
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    FOR(i, 1, k)
    {
        scanf("%d%d", &node[i].x, &node[i].y);
        swap(node[i].x, node[i].y);
    }
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = (l + r) >> 1;
    //    printf("l = %d r = %d mid = %d\n", l, r, mid);
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d", l);
    return 0;
}  
2023/4/15 16:46
加载中...