QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130232#5258. Mortgagestefanbalaz2222WA 10ms23488kbC++142.8kb2023-07-23 18:31:372023-07-23 18:31:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 18:31:39]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:23488kb
  • [2023-07-23 18:31:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<int,int> pii;

int mod=1000000+7;
const double dmod=(double)1/mod;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=2e5+10;

ll p[maxn],a[maxn],inf=1e18;
int n,q;

struct line{
    ll a,b;
    ll eval(ll x){
        return a*x+b;
    }
};
vector<line> tree[maxn*4];
ll intersect(line c1,line c2){
    ll sgn1=(c2.b-c1.b);
    ll sgn2=(c1.a-c2.a);
    if(sgn1>0)sgn1=1;
    else if(sgn1==0)sgn1=0;
    else if(sgn1<0)sgn1=-1;
    if(sgn2>0)sgn2=1;
    else if(sgn2==0)sgn2=0;
    else if(sgn2<0)sgn2=-1;
    if(sgn1*sgn2<0)return -1;
    return (c2.b-c1.b)/(c1.a-c2.a);
}


void append(vector<line>&v,line c){
    while(v.size() && intersect(v.back(),c)<0)v.pop_back();
    while(v.size()>=2 && intersect(v[v.size()-2],v[v.size()-1])>intersect(v[v.size()-2],c))v.pop_back();
    v.pb(c);
}
void build(int x,int l,int r){

    for(int i=l;i<=r;i++){
        line c;
        c.a=-i;
        c.b=p[i];
        append(tree[x],c);
    }

    if(l==r)return;

    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);

}
ll go(vector<line>&v,ll x){

    int l=0;
    int r=v.size()-1;
    int sr,ret=-1;
    while(l<=r){
        sr=(l+r)/2;

        ll inter=inf;
        if(sr<v.size()-1)inter=intersect(v[sr],v[sr+1]);

        if(x<=inter){
            r=sr-1;
            ret=sr;
        }
        else l=sr+1;

    }

    return v[ret].eval(x);
}
ll qry(int x,int l,int r,int lp,int rp,ll val){

    if(l>rp || r<lp)return inf;
    if(l>=lp && r<=rp){
        return go(tree[x],val);
    }
    int mid=(l+r)/2;
    return min(qry(x*2,l,mid,lp,rp,val),qry(x*2+1,mid+1,r,lp,rp,val));
}

int main() {


    //freopen("test.txt","r",stdin);
    //freopen("moj.txt","w",stdout);

    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        p[i]=p[i-1]+a[i];
    }

    build(1,1,n);

    while(q--){

        int lp,rp;
        scanf("%d %d",&lp,&rp);

        rp=lp+rp-1;

        ll l=0;
        ll r=1e9;
        ll x=-1;
        ll sr;
        while(l<=r){
            sr=(l+r)/2;

            ll pom=qry(1,1,n,lp,rp,sr);

            if(pom-p[lp-1]+(lp-1)*sr>=0){
                l=sr+1;
                x=sr;
            }
            else r=sr-1;

        }

        if(x<0)printf("stay with parents\n");
        else printf("%lld\n",x);

    }


    return 0;
}

詳細信息

Test #1:

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

input:

10 10
21 18 19 18 16 15 13 13 13 10
10 1
6 4
7 3
2 2
6 5
2 6
3 2
4 1
1 5
6 3

output:

10
13
13
18
12
16
18
18
18
13

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 10ms
memory: 23028kb

input:

1000 1000
196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...

output:

158
16
110
64
160
118
169
63
172
128
93
82
118
119
86
32
174
145
139
84
149
120
133
155
108
110
65
178
90
99
118
91
133
85
151
76
130
50
91
99
95
78
110
87
119
141
68
81
172
82
112
139
136
81
79
16
51
31
104
116
108
38
75
176
156
55
165
112
146
74
68
172
112
157
94
177
111
166
110
112
98
155
109
155...

result:

ok 1000 lines

Test #3:

score: 0
Accepted
time: 5ms
memory: 23172kb

input:

1000 1000
1023 912 1076 907 1015 1078 1075 1031 930 925 925 960 1013 893 1052 920 967 1046 960 1077 888 883 1045 1049 1034 1062 967 1021 986 938 871 916 901 1032 1003 1020 900 909 920 1048 884 859 1016 922 945 955 1002 1033 947 1025 970 862 929 908 912 956 873 845 933 873 921 918 904 884 1033 900 99...

output:

220
651
401
454
516
692
597
294
779
418
468
679
293
348
920
172
554
303
282
104
580
824
569
376
221
226
454
232
794
469
788
925
394
308
245
624
614
422
252
407
149
529
178
612
584
429
629
357
477
886
896
517
114
762
560
546
516
735
275
818
304
608
214
685
205
561
470
826
844
335
618
327
651
799
843
...

result:

ok 1000 lines

Test #4:

score: -100
Wrong Answer
time: 5ms
memory: 23488kb

input:

1000 1000
938 360 206 545 664 694 717 653 217 681 574 932 125 191 677 87 875 177 253 29 748 915 222 288 771 785 233 112 922 847 473 267 365 610 76 404 776 3 821 971 730 988 652 263 525 233 91 821 319 876 467 617 271 899 53 650 874 369 746 307 592 915 309 93 387 885 800 387 617 382 928 963 540 943 22...

output:

335
9
125
426
415
352
362
292
456
475
399
477
341
387
500
475
201
483
246
509
280
496
407
433
470
445
340
459
472
439
472
411
458
327
227
428
207
363
77
267
231
204
333
387
137
315
23
33
471
313
37
202
31
177
425
125
403
177
371
480
329
468
163
340
416
458
202
202
143
345
478
17
383
375
493
213
382
...

result:

wrong answer 757th lines differ - expected: '476', found: '522'