QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#522532#4403. Measuresbachbeo20070 159ms36264kbC++231.6kb2024-08-17 01:01:282024-08-17 01:01:29

Judging History

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

  • [2024-08-17 01:01:29]
  • 评测
  • 测评结果:0
  • 用时:159ms
  • 内存:36264kb
  • [2024-08-17 01:01:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
const int maxn = 200015;

int n,m,d,a[maxn],b[maxn];

struct node{
    int lt=-inf,rt=-inf,val=0,cnt=0;
    node(){}
    node(int x){
        lt=x,rt=d-x;
        val=0,cnt=d;
    }
    friend node operator+(node a,node b){
        node res;
        res.lt=max(a.lt+b.cnt,b.lt);
        res.rt=max(a.rt,a.cnt+b.rt);
        res.val=max({a.val,b.val,a.lt+b.rt});
        res.cnt=a.cnt+b.cnt;
        return res;
    }
}tree[4*maxn];
void update(int l,int r,int id,int x,int val){
    if(l==r){
        tree[id]=node(val);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(l,mid,id<<1,x,val);
    else update(mid+1,r,id<<1|1,x,val);
    tree[id]=tree[id<<1]+tree[id<<1|1];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m >> d;
    vector<pair<int,int>> com;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        com.push_back({a[i],i});
    }
    for(int i=1;i<=m;i++){
        cin >> b[i];
        com.push_back({b[i],n+i});
    }
    sort(com.begin(),com.end());
    int sz=(int)com.size();
    for(int i=1;i<=n;i++){
        int pos=lower_bound(com.begin(),com.end(),make_pair(a[i],i))-com.begin()+1;
        update(1,sz,1,pos,a[i]);
    }
    for(int i=1;i<=m;i++){
        int pos=lower_bound(com.begin(),com.end(),make_pair(b[i],n+i))-com.begin()+1;
        update(1,sz,1,pos,b[i]);
        int k=max(0LL,tree[1].val);
        cout << (double)k/2 << ' ';
    }
    cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 3ms
memory: 32004kb

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:

ok single line: '841.5 841.5 841.5 841.5 841.5 841.5 841.5 841.5 841.5 841.5 '

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 31476kb

input:

2000 10 18453
15731 19943 24157 28373 32591 36811 41033 45257 49483 53711 57941 62173 66407 70643 74881 79121 83363 87607 91853 96101 100351 104603 108857 113113 117371 121631 125893 130157 134423 138691 142961 147233 151507 155783 160061 164341 168623 172907 177193 181481 185771 190063 194357 19865...

output:

1.2242e+07 1.22471e+07 1.22522e+07 1.22574e+07 1.22625e+07 1.22676e+07 1.22727e+07 1.22778e+07 1.22829e+07 1.2288e+07 

result:

wrong answer 1st lines differ - expected: '12242000 12247120.5 12252240 1... 12277822.5 12282936 12288048.5', found: '1.2242e+07 1.22471e+07 1.22522...778e+07 1.22829e+07 1.2288e+07 '

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 14
Accepted
time: 95ms
memory: 35536kb

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:

ok single line: '167 167 167 167 167 167 167 167 167 167 '

Test #10:

score: 0
Wrong Answer
time: 89ms
memory: 36264kb

input:

200000 10 6850386
2684591 6734660 10784731 14834804 18884879 22934956 26985035 31035116 35085199 39135284 43185371 47235460 51285551 55335644 59385739 63435836 67485935 71536036 75586139 79636244 83686351 87736460 91786571 95836684 99886799 103936916 107987035 112037156 116087279 120137404 124187531...

output:

6.84539e+11 6.84542e+11 6.84545e+11 6.84549e+11 6.84552e+11 6.84556e+11 6.84559e+11 6.84563e+11 6.84566e+11 6.84569e+11 

result:

wrong answer 1st lines differ - expected: '684538602443.5 684542027636.5 ...5 684566003987.5 684569429180.5', found: '6.84539e+11 6.84542e+11 6.8454...63e+11 6.84566e+11 6.84569e+11 '

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 35
Accepted
time: 100ms
memory: 34500kb

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:

ok single line: '0 0 0 0 0 72 72 72 72 72 408.5... 3504 3504 3504 3504 3504 3504 '

Test #18:

score: 0
Wrong Answer
time: 112ms
memory: 34448kb

input:

0 200000 48068360

679 10651 18144 30601 32757 43159 49686 50125 51177 56809 58075 58226 58958 73050 94444 103453 106057 111073 122659 124138 128709 129385 131348 133922 141249 142821 143624 147761 150281 162176 163034 172312 178736 179449 181052 182053 201110 207960 209076 209076 210284 211670 2137...

output:

0 2.40292e+07 4.80596e+07 7.20876e+07 9.61207e+07 1.2015e+08 1.44181e+08 1.68215e+08 1.92248e+08 2.1628e+08 2.40313e+08 2.64347e+08 2.88381e+08 3.12408e+08 3.36432e+08 3.60461e+08 3.84494e+08 4.08526e+08 4.32554e+08 4.56588e+08 4.8062e+08 5.04653e+08 5.28687e+08 5.5272e+08 5.7675e+08 6.00783e+08 6.2...

result:

wrong answer 1st lines differ - expected: '0 24029194 48059627.5 72087579...8.5 4806287936053 4806311967223', found: '0 2.40292e+07 4.80596e+07 7.20...26e+12 4.80629e+12 4.80631e+12 '

Subtask #4:

score: 0
Wrong Answer

Test #34:

score: 41
Accepted
time: 148ms
memory: 34084kb

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:

ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ....5 3071.5 3071.5 3071.5 3071.5 '

Test #35:

score: 0
Wrong Answer
time: 159ms
memory: 35348kb

input:

0 200000 48068360

8563812 55641846 102719882 149797920 196875960 243954002 291032046 338110092 385188140 432266190 479344242 526422296 573500352 620578410 667656470 714734532 761812596 808890662 855968730 903046800 950124872 997202946 44281021 91359099 138437179 185515261 232593345 279671431 326749...

output:

0 495163 990325 1.48549e+06 1.98065e+06 2.4758e+06 2.97096e+06 3.46612e+06 3.96128e+06 4.45643e+06 4.95158e+06 5.44674e+06 5.94189e+06 6.43704e+06 6.93219e+06 7.42734e+06 7.92249e+06 8.41764e+06 8.91278e+06 9.40793e+06 9.90307e+06 1.03982e+07 3.44324e+07 5.84666e+07 8.25008e+07 1.06535e+08 1.30569e+...

result:

wrong answer 1st lines differ - expected: '0 495163 990325 1485486 198064...745 4806287940925 4806311975105', found: '0 495163 990325 1.48549e+06 1....26e+12 4.80629e+12 4.80631e+12 '