蒟蒻只AC第一个点,后面9个全WA求助

回复帖子

@nwjxjrs 2021-03-14 15:00 回复
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node1
{
    long long  x, y, l;
    long long  left, right;
}star[10005];
long long height_sorted[10005] = { 0 }, height_set[10005] = { 0 }, ans = 0;
struct node2
{
    int left;
    int right;
    long long val = 0;
    long long lazy_tag = 0;
}tree[4 * 10005];
bool cmp_x(node1 a, node1 b)
{
    return a.x < b.x;
}
void build(int num, int start, int end)
{
    tree[num].left = start, tree[num].right = end;
    if (start == end)
    {
        tree[num].val = 0;
        return;
    }
    int mid = (tree[num].left + tree[num].right) / 2;
    build(num * 2, start, mid);
    build(num * 2 + 1, mid + 1, end);
}
void spread(int num)
{
    if (tree[num].lazy_tag)
    {
        tree[num * 2].val += tree[num].lazy_tag;
        tree[num * 2 + 1].val += tree[num].lazy_tag;
        tree[num * 2].lazy_tag += tree[num].lazy_tag;
        tree[num * 2 + 1].lazy_tag += tree[num].lazy_tag;
        tree[num].lazy_tag = 0;
    }
}
void change(int num, int start, int end, long long int value)
{
    if (start <= tree[num].left && end >= tree[num].right)
    {
        tree[num].val += value;
        tree[num].lazy_tag += value;
        return;
    }
    spread(num);
    int mid = (tree[num].left + tree[num].right) / 2;
    if (start <= mid)change(num * 2, start, end, value);
    if (end > mid)change(num * 2 + 1, start, end, value);
    tree[num].val = max(tree[num * 2].val, tree[num * 2 + 1].val);
}
int main(void)
{
    int T;
    scanf("%d", &T);
    for (int k = 1; k <= T; k++)
    {
        //initial:
        int n, w, h;int top = 0;
        scanf("%d%d%d", &n, &w, &h);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld%lld%lld", &star[i].x, &star[i].y, &star[i].l);
            height_sorted[i] = star[i].y;
        }
        sort(star + 1, star + 1 + n, cmp_x);
        sort(height_sorted + 1, height_sorted + n + 1);
        for (int i = 1; i <= n; i++)
        {
            if (i == 1 || height_sorted[i] ^ height_sorted[i - 1])
                height_set[++top] = height_sorted[i];
        }
        for (int i = 1; i <= n; i++)
        {
            star[i].left = lower_bound(height_set + 1, height_set + 1 + top, star[i].y) - height_set;
            star[i].right = lower_bound(height_set + 1, height_set + 1 + top, star[i].y + h) - height_set - 1;
        }
        build(1, 1, top);
        //work:
        int tail = 1;
        for (int i = 1; i <= n; i++)
        {
            long long int j = star[i].x;
            while (star[i].x == j)
            {
                change(1, star[i].left, star[i].right, star[i].l);
                i++;
            }
            i--;
            while (tail < i && star[tail].x + w <= j)
            {
                change(1, star[tail].left, star[tail].right, -star[tail].l);
                tail++;
            }
            ans = max(ans, tree[1].val);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。