QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #327611 | #8016. 不休陀螺 | 2745518585 | 20 | 1993ms | 57072kb | C++14 | 1.6kb | 2024-02-15 11:25:15 | 2024-02-15 11:25:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000001;
int n,k,a[N],b[N];
ll f[N],g[N];
multiset<ll> Set;
namespace sgt
{
struct tree
{
int l,r;
ll s;
}T[N<<2];
void pushup(int x)
{
T[x].s=max(T[x<<1].s,T[x<<1|1].s);
}
void build(int x,int l,int r)
{
T[x].l=l,T[x].r=r;
if(l==r)
{
T[x].s=a[l]-max(a[l]-b[l],0);
return;
}
int z=l+r>>1;
build(x<<1,l,z);
build(x<<1|1,z+1,r);
pushup(x);
}
ll sum(int x,int l,int r)
{
if(T[x].l>=l&&T[x].r<=r)
{
return T[x].s;
}
int z=T[x].l+T[x].r>>1;
ll s=-1e18;
if(l<=z) s=max(s,sum(x<<1,l,r));
if(r>z) s=max(s,sum(x<<1|1,l,r));
return s;
}
}
bool check(int l,int r)
{
return k-(f[r]-f[l-1])>=sgt::sum(1,l,r);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i)
{
scanf("%d",&b[i]);
}
sgt::build(1,1,n);
for(int i=1;i<=n;++i)
{
f[i]=f[i-1]+max(a[i]-b[i],0);
g[i]=g[i-1]+(b[i]-a[i]);
}
int x=0;
ll s=0;
for(int i=1;i<=n;++i)
{
if(x<i) x=i-1;
while(x+1<=n&&check(i,x+1)) Set.insert(g[++x]);
s+=distance(Set.lower_bound(g[i-1]),Set.end());
// printf("%d %d %d\n",i,x,distance(Set.lower_bound(g[i-1]),Set.end()));
if(x>=i) Set.erase(Set.find(g[i]));
}
printf("%lld",s);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 10ms
memory: 6280kb
input:
5000 939255322 47952340 92329911 61615795 40122788 47258178 29326499 9822850 42767362 86610596 60318756 52429688 87502511 50194916 96377063 74322128 19511341 28794957 53813791 79075058 35555414 5249682 45174421 101856091 25257909 94697470 45853817 82945426 108415825 41731145 87133877 75167193 598696...
output:
1846283
result:
ok single line: '1846283'
Test #2:
score: 0
Accepted
time: 6ms
memory: 6088kb
input:
4329 694688892 165277824 152780705 114369871 103975989 100188012 147665514 101173335 39350309 37624153 95413467 157561608 10779445 35486823 19200231 55106545 50853515 35799174 92799915 152580135 158388210 132197954 75468895 66543749 104662491 59493152 108170563 22295314 152619070 77921052 105881528 ...
output:
889705
result:
ok single line: '889705'
Test #3:
score: 0
Accepted
time: 56ms
memory: 6348kb
input:
4932 10000000 879202 367773 895593 794951 253764 695611 164309 502290 638542 960084 766095 457948 783698 475707 157847 491793 196608 378324 211974 924944 42162 797172 334660 900879 522660 328814 402169 938267 498991 347773 922727 827106 16528 994043 12381 756925 642283 186848 423956 927655 344750 14...
output:
10724274
result:
ok single line: '10724274'
Test #4:
score: 0
Accepted
time: 26ms
memory: 6340kb
input:
4545 10000000 343712 838600 973396 360269 315252 660011 857231 837695 934030 232383 174532 293701 238344 367417 96713 556096 316705 468048 511763 208940 360904 853055 809137 119764 388946 415546 420603 893876 816501 899208 82913 705704 70043 223366 792251 899049 782406 849921 967761 54994 105919 384...
output:
5542899
result:
ok single line: '5542899'
Subtask #2:
score: 0
Time Limit Exceeded
Test #5:
score: 10
Accepted
time: 903ms
memory: 56296kb
input:
774484 763692678 47702350 34856775 28447988 4178162 45063720 8232662 36845607 27038945 44858289 5952529 39159657 21628528 60199611 5544054 59216841 39287087 43449994 20034684 56440004 11583811 44465341 32347476 49196492 22731571 9481143 11726859 35167370 23103544 23109378 38822668 29778048 58004104 ...
output:
124023429
result:
ok single line: '124023429'
Test #6:
score: -10
Time Limit Exceeded
input:
1000000 1145141 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 ...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #10:
score: 0
Time Limit Exceeded
input:
1000000 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 ...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #14:
score: 10
Accepted
time: 1993ms
memory: 18352kb
input:
174457 888 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1...
output:
329807918
result:
ok single line: '329807918'
Test #15:
score: -10
Time Limit Exceeded
input:
402729 5000 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 ...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #18:
score: 20
Accepted
time: 327ms
memory: 30768kb
input:
343922 773619774 0 8292680 5684115 0 0 170056 5385926 0 0 1588575 0 0 10947891 170867 35145 0 0 103085 7231562 0 0 0 0 11128944 0 4872226 0 2879880 7565181 0 8631665 0 5162564 9511835 514165 0 9628987 14357934 174784 0 12400154 0 0 8198218 0 8496060 0 0 0 0 10376826 3523227 0 14548249 0 6840016 0 0 ...
output:
36107528
result:
ok single line: '36107528'
Test #19:
score: 0
Accepted
time: 902ms
memory: 57072kb
input:
822037 644760584 0 2469002 0 5619339 0 0 0 41690 0 2840922 7972819 2323916 0 7218270 0 0 6647344 1095198 0 5412830 6654778 0 4588035 0 5181193 5073101 0 0 0 2371931 2740725 6756043 4534813 1080318 3180435 0 0 0 7537979 0 9432571 3034547 1737404 7266942 0 0 5894473 2658989 0 3648760 6086440 768115 16...
output:
117551199
result:
ok single line: '117551199'
Test #20:
score: 0
Accepted
time: 196ms
memory: 30200kb
input:
318889 580944500 0 53440448 62414510 4444108 16412385 37171101 0 0 65074099 0 0 0 0 0 0 1736666 40422852 25240303 0 0 48581689 0 51050599 0 25918077 0 1579933 0 0 6387116 64336506 0 0 21191911 1157620 0 63412896 28547264 15735514 28842299 56755053 1569652 18413574 0 0 38907260 13487516 3629386 0 0 3...
output:
6426676
result:
ok single line: '6426676'
Test #21:
score: 0
Accepted
time: 438ms
memory: 52916kb
input:
634480 869644773 24926780 0 0 5806548 29345967 0 0 24585164 5082228 0 36723829 0 45565685 38830813 40656683 0 43901325 0 0 24818007 0 9578233 0 29516514 0 45637396 0 17904712 3102583 29421661 0 17144626 0 26616707 20864851 30084372 0 13288472 33594305 10029647 27932498 0 37897745 5476038 0 0 0 0 0 0...
output:
24380270
result:
ok single line: '24380270'
Test #22:
score: -20
Time Limit Exceeded
input:
343922 773619774 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 8425454 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11326 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...
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #24:
score: 0
Time Limit Exceeded
input:
468676 582048177 6889433 7293342 20676061 15545414 4911497 12352219 8921719 1705801 19695926 25259227 2645394 17518171 19753552 9449377 982708 22479531 1267985 15594372 20685422 9627290 2017543 6459134 18614020 16206301 14962487 12932255 7101003 29140540 6479702 20607124 2540287 15565156 20274141 11...
output:
353280708