QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641096#5069. VacationRikku_eqWA 1748ms50548kbC++148.3kb2024-10-14 18:29:012024-10-14 18:29:03

Judging History

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

  • [2024-10-14 18:29:03]
  • 评测
  • 测评结果：WA
  • 用时：1748ms
  • 内存：50548kb
查看
  • [2024-10-14 18:29:01]
  • 提交

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); }
        tr[u].seq=max(tr[ls(u)].seq, tr[rs(u)].seq);
        tr[u].sum=max(tr[ls(u)].sum, tr[rs(u)].sum);
    }
    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 i=1; i<=bid[n]; i++) {
    //     cout<<ST1.qry(ST1.rt, 1, n, st[i], st[i+1]-1).sum<<" ";
    // }
    // cout<<endl;

    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-1]], r-C).sum);
                ans=max(ans, ST1.qry(ST1.rt, 1, n, l, st[bid[l+1]]-1).sum);
            }

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

        // cout<<"t: "<<t<<endl;
        // for (int i=1; i<=bid[n]; i++) {
        //     cout<<ST1.qry(ST1.rt, 1, n, st[i], st[i+1]-1).sum<<" ";
        //     cout<<ST1.qry_seq(ST1.rt, 1, n, st[i], st[i+1]-1).seq<<endl;
        // }
        // cout<<endl;
        // else {
        //     int l, r; scanf("%d %d", &l, &r);
        // }
    }

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

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 8032kb

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: 1748ms
memory: 50548kb

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
1241695282
999343404
999847372
1288440931
998160312
1288440931
1248682868
1288440931
1248682868
1288440931
1288440931
1248682868
999876122
999981999
1288440931
1248682868
1288440931
1241695282
999723649
1288440931
999957587
1288440931
1248682868
1288440931
1248682868
1288440931
1288440931
...

result:

wrong answer 2nd numbers differ - expected: '999981999', found: '1241695282'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 21:40:08 | 開源專案