QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138084#4403. Measurespatrik010 458ms26864kbC++203.5kb2023-08-10 22:21:312023-08-10 22:21:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 22:21:32]
  • 评测
  • 测评结果:0
  • 用时:458ms
  • 内存:26864kb
  • [2023-08-10 22:21:31]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define i32 int
#define i64 long long
#define f64 double
#define F0R(i, n) for(int i = 0; i<n; i++)
#define FOR(i, s, e) for(int i = s; i<e; i++)
#define vec vector
#define arr array

struct SegNode {
    arr<i64, 2> mx{-1, 0};
    arr<i64, 2> mn{-1, 0};
};

struct SegTree {
    i32 n;
    vec<SegNode> data;
    vec<i64> lazy;

    SegTree(i32 in) {
        n = 1;
        while(n<in) {
            n*=2;
        }
        data = vec<SegNode>(n*2);
        lazy = vec<i64>(n*2);
    }

    void propagate(i32 i) {
        data[i].mn[1] += lazy[i];
        data[i].mx[1] += lazy[i];
        if(i*2 < n*2) {
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }
    
    SegNode merge(SegNode l, SegNode r) {
        if(l.mn[0] == -1) {
            return r;
        }
        else if(r.mn[0] == -1) {
            return l;
        }

        SegNode res = {};
        if(l.mx[0]+l.mx[1] > r.mx[0]+r.mx[1]) {
            res.mx = l.mx;
        }
        else {
            res.mx = r.mx;
        }
        if(l.mn[0] + l.mn[1] < r.mn[0]+r.mn[1]) {
            res.mn = l.mn;
        }
        else {
            res.mn = r.mn;
        }

        return res;
    }

    SegNode query(i32 l, i32 r, i32 i = 1, i32 ll = 0, i32 rr =  -1) {
        if(rr==-1) rr = n;

        if(ll>=r || rr<=l) {
            return {};
        }
        propagate(i);

        if(ll>=l && rr <=r) {
            return data[i];
        }

        i32 m = (ll+rr)/2;
        SegNode left = query(l, r, i*2, ll, m);
        SegNode right = query(l, r, i*2+1, m, rr);

        return merge(left, right);
    }

    void update(i32 l, i32 r, i64 add, i32 i = 1, i32 ll = 0, i32 rr = -1) {
        if(rr==-1) rr = n;

        propagate(i);

        if(ll>=r || rr <= l) {
            return;
        }


        if(ll>=l && rr<=r) {
            lazy[i] += add;
            propagate(i);
            return;
        }

        i32 m = (ll+rr)>>1;
        update(l, r, add, (i<<1), ll, m);
        update(l, r, add, (i<<1)+1, m, rr);

        data[i] = merge(data[(i<<1)], data[(i<<1)+1]);
    }

    void set(i32 i, i32 val) {
        update(i, i+1, 0); // to propagate all the nodes up to my value
        i+=n;
        // cerr<<data[i].mx[0] <<endl;
        assert(data[i].mx[0] == -1);
        data[i].mx[0] = val;
        data[i].mn[0] = val;
        while(i>1) {
            i>>=1;
            data[i] = merge(data[i<<1], data[(i<<1)+1]);
        }
    }
};

i32 main() {
    cout << setprecision(15);

    i32 n, m, d;
    cin >> n >> m >> d;

    SegTree st(n+m);

    vec<arr<i32, 2>> v(n+m);

    F0R(i, n) {
        cin >> v[i][0];
        v[i][1] = i;
    }

    F0R(i, m) {
        cin >> v[i+n][0];
        v[i+n][1] = i+n;
    }

    auto v_s = v;
    sort(v_s.begin(), v_s.end());

    F0R(i, n+m) {
        v[v_s[i][1]][1] = i;
    }

    i64 ans = 0;

    auto add = [&](i32 i) {
        i32 j = v[i][1];
        st.update(j, n+m, -d);
        st.set(j, v[i][0]);

        SegNode l = st.query(0, j+1);
        i64 lval = l.mx[0]+l.mx[1];
        SegNode r = st.query(j, n+m);
        i64 rval = r.mn[0]+r.mn[1];
        
        ans = max(ans, lval-rval);
    };

    F0R(i, n) {
        add(i);
    }

    F0R(i, m) {
        add(i+n);
        cout << ((f64)ans)/2.0 << '\n';
    }
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3716kb

input:

2000 10 1845
533219610 452539353 832124174 883897563 447321676 368976465 166536135 758380924 920827481 313174994 781707618 815047867 925081003 325012331 69086835 637564067 429273345 781597586 376641056 72157101 36547962 656170271 772458737 707141316 33546435 166034841 747620387 663158697 852912826 9...

output:

841.5
841.5
841.5
841.5
841.5
841.5
841.5
841.5
841.5
841.5

result:

wrong answer 1st lines differ - expected: '841.5 841.5 841.5 841.5 841.5 841.5 841.5 841.5 841.5 841.5', found: '841.5'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 387ms
memory: 26832kb

input:

200000 10 128
853561279 93820692 821887507 753094209 227461682 691969137 519378763 296675314 646705609 727762559 98496302 959430593 403972779 982596953 775241610 209602833 112152326 762927950 619981024 764326855 379819398 392809293 145648647 960106249 514225957 952027167 428472167 571874662 95085242...

output:

167
167
167
167
167
167
167
167
167
167

result:

wrong answer 1st lines differ - expected: '167 167 167 167 167 167 167 167 167 167', found: '167'

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 0
Wrong Answer
time: 364ms
memory: 26816kb

input:

0 200000 1289

3822 6378 8930 10621 14339 15484 27804 30714 47103 51268 51740 57420 74974 81161 81292 82797 84329 92397 96558 102781 108313 117355 117730 121011 121917 123170 124479 132083 144850 152609 153404 161406 162584 163062 172029 172074 172504 178451 185861 197247 197729 204944 223883 245287...

output:

0
0
0
0
0
72
72
72
72
72
408.5
408.5
408.5
408.5
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
579
622
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
1051.5
10...

result:

wrong answer 1st lines differ - expected: '0 0 0 0 0 72 72 72 72 72 408.5...4 3504 3504 3504 3504 3504 3504', found: '0'

Subtask #4:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 458ms
memory: 26864kb

input:

0 200000 1289

582772771 851704216 915624354 601264573 510202549 844706968 795870015 897865316 665295826 172582259 59358299 239645315 343442424 973625659 840972987 546781500 897704802 602265737 968590815 561687707 728916679 417806750 143659623 620408739 86393298 403049850 578760184 735385586 7656173...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st lines differ - expected: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...1.5 3071.5 3071.5 3071.5 3071.5', found: '0'