线段树写法,只过了subtask1

P1725 琪露诺

花园Serena @ 2020-11-09 18:51:36

RT,用的线段树写法,但是被subtask2给hack掉了,不知道错在哪里,求解答,代码如下

#include <bits/stdc++.h>
using namespace std;
#define rg register int
#define mid ((x + y) >> 1)
#define rs (i << 1 | 1)
#define ls (i << 1)
const int MAXN = 200000 + 10;
int n, L, R, t[(MAXN << 2) + 10], a[MAXN << 1];
int mx, f[MAXN << 1], Max = -0x7fffffff;
void inline built (int i, int x, int y) {
    if(x == y) {t[i] = a[x]; return;}
    built (ls, x, mid); built(rs, mid + 1, y);
    t[i] = max(t[rs], t[ls]);
}
int inline ans (int i, int x, int y, int l, int r) {
    if(x > r || y < l) return -0x7fffffff;
    if(x >= l && y <= r) return t[i];
    return max(ans(rs, mid + 1, y, l, r), ans(ls, x, mid , l, r));

}
void inline change(int i, int x, int y,int l, int w) {
    if(x == y) {t[i] = w; return;}
    if(l <= mid) change(ls, x, mid, l, w);
    else change(rs, mid + 1, y, l, w);
    t[i] = max(t[rs], t[ls]);
}
int main() {
    scanf("%d%d%d", &n, &L, &R);
    for(rg i = 0; i <= n; i ++)
        scanf("%d", &a[i]);
    for(rg i = L; i <= n + R; i ++) {
        if(i - R < 0) mx = ans(1, 0, n, 0, i - L);
        else mx = ans(1, 0, n, i - R, i - L);
        f[i] = mx + a[i]; change(1, 0, n, i, f[i]);
        if(i >= n) Max = max(f[i], Max);
    }
    printf("%d\n", Max);
    return 0;
}

by 花园Serena @ 2020-11-09 19:29:46

已AC


by 君怜 @ 2020-11-16 15:03:46

@花园Serena 看到你了!


by 花园Serena @ 2020-11-16 15:52:56

@君怜 草,你这是翻了多久啊


by 君怜 @ 2020-11-16 16:23:51

@花园Serena 没有没有,我恰好做这题了,看到讨论里有这个就点开了,结果发现是你哈哈哈哈


by 花园Serena @ 2020-11-16 16:41:11

@君怜 草,来和我做大魔法师 戳这里


by 花园Serena @ 2020-11-16 16:42:01

@君怜 你还没有关注我,你原来都关注了的(哭)


|