QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641077#5069. VacationRikku_eqWA 1359ms50064kbC++147.8kb2024-10-14 18:20:572024-10-14 18:20:58

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 18:20:58]
  • 评测
  • 测评结果：WA
  • 用时：1359ms
  • 内存：50064kb
查看
  • [2024-10-14 18:20:57]
  • 提交

answer

#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000000000000
#define ls(u) tr[u].ls
#define rs(u) tr[u].rs
using namespace std;
typedef long long ll;

int n, m, C, rec[N*2];
int bid[N], st[N];
ll _f[N], _g[N];

struct SegT1
{
    struct Seg { int ls, rs; ll f, g, sum, tgf, tgg; ll seq, lseq, rseq, aseq; } tr[N*2];
    int rt, tot;
    struct RET { ll f, g, sum; };
    struct RET2 { ll seq, lseq, rseq, aseq; };

    void pushdown (int u)
    {
        ll valf=tr[u].tgf, valg=tr[u].tgg;
        tr[ls(u)].f+=valf; tr[ls(u)].tgf+=valf; tr[ls(u)].sum+=valf;
        tr[rs(u)].f+=valf; tr[rs(u)].tgf+=valf; tr[rs(u)].sum+=valf;
        tr[ls(u)].g+=valg; tr[ls(u)].tgg+=valg; tr[ls(u)].sum+=valg;
        tr[rs(u)].g+=valg; tr[rs(u)].tgg+=valg; tr[rs(u)].sum+=valg;
        tr[u].tgf=0; tr[u].tgg=0;
    }
    void merge (int u)
    {
        tr[u].f=max(tr[ls(u)].f, tr[rs(u)].f);
        tr[u].g=max(tr[ls(u)].g, tr[rs(u)].g);
        tr[u].sum=max(tr[ls(u)].f+tr[rs(u)].g, max(tr[ls(u)].sum, tr[rs(u)].sum));
    }

    void build (int &u, int l, int r)
    {
        tr[u]=(Seg){ ls(u), rs(u), -INF, -INF, -INF, 0, 0, -INF, -INF, -INF, 0 };
        if (!u) { u=++tot; }
        if (l==r) {
            tr[u].f=_f[l+C]; tr[u].g=_g[l];
            tr[u].seq=rec[l];
            tr[u].lseq=rec[l];
            tr[u].rseq=rec[l];
            tr[u].aseq=rec[l];
            return;
        }
        int md=(l+r)>>1;
        build(ls(u), l, md);
        build(rs(u), md+1, r);
        merge(u);

        tr[u].seq=max(tr[ls(u)].rseq+tr[rs(u)].lseq, max(tr[ls(u)].seq, tr[rs(u)].seq));
        tr[u].lseq=max(tr[ls(u)].lseq, tr[ls(u)].aseq+tr[rs(u)].lseq);
        tr[u].rseq=max(tr[rs(u)].rseq, tr[rs(u)].aseq+tr[ls(u)].rseq);
        tr[u].aseq=tr[ls(u)].aseq+tr[rs(u)].aseq;
    }

    void add_g (int u, int l, int r, int ql, int qr, ll num)
    {
        if (ql>r || qr<l) { return; }
        if (ql<=l && r<=qr) { tr[u].g+=num; tr[u].tgg+=num; tr[u].sum+=num; return; }
        pushdown(u);
        int md=(l+r)>>1;
        add_g(ls(u), l, md, ql, qr, num);
        add_g(rs(u), md+1, r, ql, qr, num);
        merge(u);
    }
    void add_f (int u, int l, int r, int ql, int qr, ll num)
    {
        if (ql>r || qr<l) { return; }
        if (ql<=l && r<=qr) { tr[u].f+=num; tr[u].tgf+=num; tr[u].sum+=num; return; }
        pushdown(u);
        int md=(l+r)>>1;
        add_f(ls(u), l, md, ql, qr, num);
        add_f(rs(u), md+1, r, ql, qr, num);
        merge(u);
    }
    RET qry (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return (RET){ -INF, -INF, -INF }; }
        if (ql<=l && r<=qr) { return (RET){ tr[u].f, tr[u].g, tr[u].sum }; }
        pushdown(u);
        int md=(l+r)>>1;
        RET resl=qry(ls(u), l, md, ql, qr);
        RET resr=qry(rs(u), md+1, r, ql, qr);
        return (RET){ max(resl.f, resr.f), max(resl.g, resr.g), max(resl.f+resr.g, max(resl.sum, resr.sum)) };
    }

    void upd_seq (int u, int l, int r, int id, ll num)
    {
        if (l==r) { tr[u].seq=tr[u].lseq=tr[u].rseq=tr[u].aseq=num; return; }
        int md=(l+r)>>1;
        if (id<=md) { upd_seq(ls(u), l, md, id, num); }
        else { upd_seq(rs(u), md+1, r, id, num); }

        tr[u].seq=max(tr[ls(u)].rseq+tr[rs(u)].lseq, max(tr[ls(u)].seq, tr[rs(u)].seq));
        tr[u].lseq=max(tr[ls(u)].lseq, tr[ls(u)].aseq+tr[rs(u)].lseq);
        tr[u].rseq=max(tr[rs(u)].rseq, tr[rs(u)].aseq+tr[ls(u)].rseq);
        tr[u].aseq=tr[ls(u)].aseq+tr[rs(u)].aseq;
    }
    RET2 qry_seq (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return (RET2){ -INF, -INF, -INF, 0 }; }
        if (ql<=l && r<=qr) { return (RET2){ tr[u].seq, tr[u].lseq, tr[u].rseq, tr[u].aseq }; }
        int md=(l+r)>>1;
        RET2 resl=qry_seq(ls(u), l, md, ql, qr);
        RET2 resr=qry_seq(rs(u), md+1, r, ql, qr);
        RET2 res;
        res.seq=max(resl.rseq+resr.lseq, max(resl.seq, resr.seq));
        res.lseq=max(resl.lseq, resl.aseq+resr.lseq);
        res.rseq=max(resr.rseq, resr.aseq+resl.rseq);
        res.aseq=resl.aseq+resr.aseq;
        return res;
    }
} ST1;

struct SegT2
{
    struct Seg { int ls, rs; ll seq, sum; } tr[N*2];
    int rt, tot;

    void build (int &u, int l, int r)
    {
        if (!u) { u=++tot; }
        if (l==r) {
            tr[u].seq=ST1.qry_seq(ST1.rt, 1, n, st[bid[l]], st[bid[l+1]]-1).seq;
            tr[u].sum=ST1.qry(ST1.rt, 1, n, st[bid[l]], st[bid[l+1]]-1).sum;
            return;
        }
        int md=(l+r)>>1;
        build(ls(u), l, md); build(rs(u), md+1, r);
        tr[u].seq=max(tr[ls(u)].seq, tr[rs(u)].seq);
        tr[u].sum=max(tr[ls(u)].sum, tr[rs(u)].sum);
    }
    void upd (int u, int l, int r, int id, ll sum, ll seq)
    {
        if (l==r) { tr[u].sum=sum; tr[u].seq=seq; return; }
        int md=(l+r)>>1;
        if (id<=md) { upd(ls(u), l, md, id, sum, seq); }
        else { upd(rs(u), md+1, r, id, sum, seq); }
    }
    ll qry_seq (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return -INF; }
        if (ql<=l && r<=qr) { return tr[u].seq; }
        int md=(l+r)>>1;
        return max(qry_seq(ls(u), l, md, ql, qr), qry_seq(rs(u), md+1, r, ql, qr));
    }
    ll qry_sum (int u, int l, int r, int ql, int qr)
    {
        if (ql>r || qr<l) { return -INF; }
        if (ql<=l && r<=qr) { return tr[u].sum; }
        int md=(l+r)>>1;
        return max(qry_sum(ls(u), l, md, ql, qr), qry_sum(rs(u), md+1, r, ql, qr));
    }
    void uupd (int pos, ll sum, ll seq)
    {
        upd(rt, 1, bid[n], pos, sum, seq);
    }

} ST2;


void uupd (int pos, int num)
{
    ll ad=num-rec[pos];
    ST1.add_g(ST1.rt, 1, n, st[bid[pos]], pos, ad);
    if (bid[pos]>1) { ST1.add_f(ST1.rt, 1, n, pos-C, st[bid[pos]]-1, ad); }
    ST1.upd_seq(ST1.rt, 1, n, pos, num);
    rec[pos]=num;

    ST2.uupd(bid[pos], ST1.qry(ST1.rt, 1, n, st[bid[pos]], st[bid[pos]+1]-1).sum, ST1.qry_seq(ST1.rt, 1, n, st[bid[pos]], st[bid[pos]+1]-1).seq);
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d %d %d", &n, &m, &C);
    for (int i=1; i<=n; i++) { scanf("%d", &rec[i]); }

    for (int i=1; i<=n; i++) {
        bid[i]=((i-1)/C)+1;
        if (!st[bid[i]]) { st[bid[i]]=i; }
    } st[bid[n]+1]=n+1;

    for (int i=1; i<=n; i++) {
        _f[i]=(i!=st[bid[i]])*_f[i-1]+rec[i];
    }
    for (int i=n; i>=1; i--) {
        _g[i]=(i!=st[bid[i]+1]-1)*_g[i+1]+rec[i];
    }

    ST1.build(ST1.rt, 1, n);
    ST2.build(ST2.rt, 1, bid[n]);

    for (int t=1; t<=m; t++) {
        int op; scanf("%d", &op);
        if (op==1) {
            int x, y; scanf("%d %d", &x, &y); uupd(x, y);
        }
        else {
            int l, r; scanf("%d %d", &l, &r);

            ll ans=0;
            if (r-l+1<=C) { ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, l, r).seq); }
            else if (bid[l]==bid[r]-1) {
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, l, l+C-1).seq);
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, r-C+1, r).seq);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, l, r-C).sum);
            }
            else {
                ans=max(ans, ST2.qry_seq(ST2.rt, 1, bid[n], bid[l]+1, bid[r]-1));
                if (bid[l]<bid[r]-2) {
                    ans=max(ans, ST2.qry_sum(ST2.rt, 1, bid[n], bid[l]+1, bid[r]-2));
                }
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, l, l+C-1).seq);
                ans=max(ans, ST1.qry_seq(ST1.rt, 1, n, r-C+1, r).seq);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, st[bid[r]], r-C).sum);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, l, st[bid[l+1]]-1).sum);
            }

            printf("%lld\n", ans);
        }
    }

    return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10072kb

input:

5 6 3
0 -5 -3 8 -3
2 3 5
1 2 5
2 1 5
1 4 -3
2 3 5
2 1 5

output:

8
10
0
5

result:

ok 4 number(s): "8 10 0 5"

Test #2:

score: -100
Wrong Answer
time: 1359ms
memory: 50064kb

input:

200000 500000 1
387060158 961744470 37167782 737122872 -532977662 1604246 -30977399 871848791 444997246 454204578 -813187501 -660394286 448014171 -835115276 -631880452 887715308 258530352 805589560 -414653327 -156732249 -335096199 -80266237 367896009 738406627 -903652056 446120866 415658444 -1347916...

output:

999902477
999981999
999343404
999847372
999957587
998160312
999981999
999981999
999981999
999980061
999981999
999981999
999981999
999876122
999981999
999996602
999981999
999981999
999981999
999723649
999981999
999957587
999896087
999981999
999981999
999981999
999981999
999981999
999957587
999981999
...

result:

wrong answer 622nd numbers differ - expected: '999932568', found: '999921057'
English 繁體中文 简体中文

服务器时间: 2024-12-02 22:30:19 | 开源项目