QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #85510 | #5657. Hungry Cow | AFewSuns | 0 | 3142ms | 514840kb | C++14 | 3.5kb | 2023-03-07 20:18:24 | 2023-03-07 20:19:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
#define int ll
#define mod 1000000007
#define LC lc[x]
#define RC rc[x]
map<ll,ll> mp;
vector<ll> vec[400040];
vector<int*> st;
vector<int > sta;
ll n,V=2e14,inv2=(mod+1)>>1,d[100010],b[100010];
int rt=0,top=0,tot=0,lc[10000010],rc[10000010],sum[10000010];
ll tree[10000010];
void ins(ll x,ll l,ll r,ll ql,ll qr,ll v){
if(ql<=l&&r<=qr){
vec[x].push_back(v);
return;
}
ll mid=(l+r)>>1;
if(ql<=mid) ins(x<<1,l,mid,ql,qr,v);
if(mid<qr) ins(x<<1|1,mid+1,r,ql,qr,v);
}
il ll S(ll l,ll r){
return (l+r)%mod*((r-l+1)%mod)%mod*inv2%mod;
}
il void pushup(ll x){
tree[x]=tree[LC]+tree[RC];
sum[x]=(sum[LC]+sum[RC])%mod;
}
void mdf(int &x,ll l,ll r,ll ql,ll qr){
if(!x){
if(!sta.empty()){
x=sta.back();
sta.pop_back();
}
else x=++tot;
LC=RC=0;
}
if(tree[x]==(r-l+1)) return;
st.push_back(&x);
if(ql<=l&&r<=qr){
tree[x]=r-l+1;
sum[x]=S(l,r);
return;
}
ll mid=(l+r)>>1;
if(ql<=mid) mdf(LC,l,mid,ql,qr);
if(mid<qr) mdf(RC,mid+1,r,ql,qr);
pushup(x);
}
ll querycnt(ll x,ll l,ll r,ll ql,ll qr){
if(ql>qr||tree[x]==(r-l+1)) return 0;
if(ql<=l&&r<=qr) return r-l+1-tree[x];
ll mid=(l+r)>>1,res=0;
if(ql<=mid) res+=querycnt(LC,l,mid,ql,qr);
if(mid<qr) res+=querycnt(RC,mid+1,r,ql,qr);
return res;
}
ll query(ll x,ll l,ll r,ll k){
if(l==r) return l;
ll mid=(l+r)>>1;
if((mid-l+1-tree[LC])>=k) return query(LC,l,mid,k);
else return query(RC,mid+1,r,k-(mid-l+1-tree[LC]));
}
void recycle(ll tmp){
while((ll)st.size()>tmp){
int &x=*st.back();
pushup(x);
if(!tree[x]){
sta.push_back(x);
x=0;
}
st.pop_back();
}
}
void solve(ll x,ll l,ll r){
ll tmp=st.size();
fr(i,0,(ll)vec[x].size()-1){
ll id=vec[x][i],cnt=querycnt(rt,1,V,1,d[id]-1);
ll pos=query(rt,1,V,cnt+b[id]);
mdf(rt,1,V,d[id],pos);
}
if(l<=12501&&12501<=r) pf("%lld %lld %lld %lld\n",x,l,r,sum[rt]);
if(l==r) /*writeln(sum[rt])*/;
else{
ll mid=(l+r)>>1;
solve(x<<1,l,mid);
solve(x<<1|1,mid+1,r);
}
recycle(tmp);
}
main(){
n=read();
fr(i,1,n){
d[i]=read();
b[i]=read();
if(mp.count(d[i])){
ll tmp=mp[d[i]];
ins(1,1,n,tmp,i-1,tmp);
}
mp[d[i]]=i;
}
for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++){
ll tmp=(*it).sec;
ins(1,1,n,tmp,n,tmp);
}
solve(1,1,n);
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 12920kb
input:
3 4 3 1 5 1 2
output:
result:
wrong answer Answer contains longer sequence [length = 3], but output contains 0 elements
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 14056kb
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
result:
wrong answer Answer contains longer sequence [length = 9], but output contains 0 elements
Test #3:
score: 0
Wrong Answer
time: 53ms
memory: 27304kb
input:
5000 1 255364995 414918035 212844 1 112266691 321122438 191414 1 277615842 848755093 61676 1 432591689 892259443 53755 1 263753018 173404455 173565 1 178341924 878941367 221276 1 65332960 439468128 240741 1 812238377 191076090 108732 1 180383041 927440330 112995 1 595696140 579818784 85614 1 5057816...
output:
result:
wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements
Test #4:
score: 0
Wrong Answer
time: 2318ms
memory: 514840kb
input:
100000 1 500000000 1000000001 500000000 2000000001 500000000 3000000001 500000000 4000000001 500000000 5000000001 500000000 6000000001 500000000 7000000001 500000000 8000000001 500000000 9000000001 500000000 10000000001 500000000 11000000001 500000000 12000000001 500000000 13000000001 500000000 1400...
output:
1 1 100000 375000007 2 1 50000 375000007 4 1 25000 375000007 9 12501 25000 789270309 18 12501 18750 789270309 36 12501 15625 789270309 72 12501 14063 789270309 144 12501 13282 789270309 288 12501 12891 789270309 576 12501 12696 789270309 1152 12501 12598 789270309 2304 12501 12549 789270309 4608 125...
result:
wrong answer 1st numbers differ - expected: '375000007', found: '1'
Test #5:
score: 0
Wrong Answer
time: 2888ms
memory: 273712kb
input:
100000 49998999950002 500000000 49997999950003 500000000 49996999950004 500000000 49995999950005 500000000 49994999950006 500000000 49993999950007 500000000 49992999950008 500000000 49991999950009 500000000 49990999950010 500000000 49989999950011 500000000 49988999950012 500000000 49987999950013 500...
output:
1 1 100000 0 2 1 50000 376399979 4 1 25000 376399979 9 12501 25000 188429558 18 12501 18750 188429558 36 12501 15625 188429558 72 12501 14063 188429558 144 12501 13282 188429558 288 12501 12891 188429558 576 12501 12696 188429558 1152 12501 12598 188429558 2304 12501 12549 188429558 4608 12501 12525...
result:
wrong answer 1st numbers differ - expected: '376399979', found: '1'
Test #6:
score: 0
Wrong Answer
time: 1626ms
memory: 209712kb
input:
100000 92303348842417 121458 92270522994821 852054850 93765096269940 752161890 97779083359973 984327853 90030769679569 439157849 99462493683485 45660 95578441605501 614317411 92236129196525 474149928 96065411631989 429943696 90394247621798 382840249 89263934750729 791122796 93577089467158 99679481 9...
output:
1 1 100000 0 2 1 50000 0 4 1 25000 0 9 12501 25000 376074096 18 12501 18750 6261127 36 12501 15625 403357848 72 12501 14063 349803805 144 12501 13282 55915785 288 12501 12891 834310785 576 12501 12696 490791896 1152 12501 12598 282058642 2304 12501 12549 916114328 4608 12501 12525 681574575 9216 125...
result:
wrong answer 1st numbers differ - expected: '601385635', found: '1'
Test #7:
score: 0
Wrong Answer
time: 1624ms
memory: 209380kb
input:
100000 98001410246890 641673458 94816407430628 495030536 95979591652947 43208 95979591652947 183686 97163521776290 904784415 91640049592559 875129980 95914835187460 844802426 94846379383324 974270031 99639652388956 311664277 99298294827771 913614463 99476866913169 221766107 97248342663994 669489020 ...
output:
1 1 100000 805408268 2 1 50000 805408268 4 1 25000 805408268 9 12501 25000 540650401 18 12501 18750 900692238 36 12501 15625 814932339 72 12501 14063 507178795 144 12501 13282 699538311 288 12501 12891 256776543 576 12501 12696 660737453 1152 12501 12598 289858015 2304 12501 12549 772136934 4608 125...
result:
wrong answer 1st numbers differ - expected: '805408268', found: '1'
Test #8:
score: 0
Wrong Answer
time: 1634ms
memory: 213768kb
input:
100000 97338601145206 191999210 97657969728741 875988993 92559675348135 8552565 99354409480201 960853995 93648768326445 343671323 97400841247229 104463842 98844341051398 508718383 96144328794112 187050711 98030257583732 365513 92378049740181 852725611 98301676983212 360931360 99458914124366 80234576...
output:
1 1 100000 201835835 2 1 50000 201835835 4 1 25000 201835835 9 12501 25000 53286082 18 12501 18750 879680694 36 12501 15625 889161963 72 12501 14063 709835068 144 12501 13282 293936623 288 12501 12891 141467479 576 12501 12696 821350634 1152 12501 12598 463882833 2304 12501 12549 589405913 4608 1250...
result:
wrong answer 1st numbers differ - expected: '201835835', found: '1'
Test #9:
score: 0
Wrong Answer
time: 1564ms
memory: 219704kb
input:
100000 96119987448606 658315028 98644701118435 280992389 98180676447908 56168 99822794299596 237183170 94655838918825 563695131 95744558879343 686204820 93739311062176 263266841 97630990881452 96901680 98683433984282 380708175 98141920320037 147598812 98095513966598 814629225 97882900659205 55097258...
output:
1 1 100000 284288958 2 1 50000 284288958 4 1 25000 284288958 9 12501 25000 117541838 18 12501 18750 618241761 36 12501 15625 573128870 72 12501 14063 95499666 144 12501 13282 176158844 288 12501 12891 230751429 576 12501 12696 552617630 1152 12501 12598 38137823 2304 12501 12549 650602288 4608 12501...
result:
wrong answer 1st numbers differ - expected: '284288958', found: '1'
Test #10:
score: 0
Wrong Answer
time: 1461ms
memory: 220672kb
input:
100000 98169641631056 170946511 99452522210742 393032132 98797460964704 393706377 98747209012224 529219651 99152468691953 362194103 99410753036475 215295 97096873124809 1315725 96106202009957 124516158 95176405230280 853965254 99359463136784 622839995 96635771520630 550456203 96368792029394 93630831...
output:
1 1 100000 692991104 2 1 50000 692991104 4 1 25000 692991104 9 12501 25000 475055425 18 12501 18750 228005657 36 12501 15625 933043307 72 12501 14063 718295241 144 12501 13282 775288263 288 12501 12891 376196516 576 12501 12696 302560608 1152 12501 12598 417271682 2304 12501 12549 390810953 4608 125...
result:
wrong answer 1st numbers differ - expected: '692991104', found: '1'
Test #11:
score: 0
Wrong Answer
time: 1397ms
memory: 210712kb
input:
100000 97499080763005 475255826 97499083333242 9347 97499080763005 395470349 97499924236501 4654 97499080763005 148122052 97499213182916 2365 97499080763005 544025506 97499777050346 9912 97499080763005 41736833 97499401163067 12607 97499080763005 127843558 97499125181305 7144 97499080763005 13152858...
output:
1 1 100000 0 2 1 50000 0 4 1 25000 0 9 12501 25000 173254770 18 12501 18750 173254770 36 12501 15625 173254770 72 12501 14063 173254770 144 12501 13282 173254770 288 12501 12891 173254770 576 12501 12696 173254770 1152 12501 12598 173254770 2304 12501 12549 173254770 4608 12501 12525 173254770 9216 ...
result:
wrong answer 1st numbers differ - expected: '655956691', found: '1'
Test #12:
score: 0
Wrong Answer
time: 1406ms
memory: 208580kb
input:
100000 98999026537234 929244389 98999182418499 5182 98999026537234 774643967 98999646433835 17857 98999026537234 760743518 98999980664456 7597 98999026537234 573421161 98999090975969 6621 98999026537234 95191521 98999947586610 17798 98999026537234 953104244 98999116462517 15643 98999026537234 100617...
output:
1 1 100000 0 2 1 50000 0 4 1 25000 0 9 12501 25000 281165229 18 12501 18750 281165229 36 12501 15625 281165229 72 12501 14063 281165229 144 12501 13282 281165229 288 12501 12891 281165229 576 12501 12696 281165229 1152 12501 12598 281165229 2304 12501 12549 281165229 4608 12501 12525 281165229 9216 ...
result:
wrong answer 1st numbers differ - expected: '526240962', found: '1'
Test #13:
score: 0
Wrong Answer
time: 1246ms
memory: 370096kb
input:
100000 99499024212061 630391525 99499061152079 3864 99499024212061 16505706 99499878275777 4812 99499024212061 776185964 99499757280269 12059 99499024212061 356565635 99499399237611 8902 99499024212061 972528120 99499256994518 9171 99499024212061 419476867 99499909552451 17146 99499024212061 6767939...
output:
1 1 100000 0 2 1 50000 0 4 1 25000 0 9 12501 25000 34904386 18 12501 18750 34904386 36 12501 15625 34904386 72 12501 14063 34904386 144 12501 13282 34904386 288 12501 12891 34904386 576 12501 12696 34904386 1152 12501 12598 34904386 2304 12501 12549 34904386 4608 12501 12525 34904386 9216 12501 1251...
result:
wrong answer 1st numbers differ - expected: '358833000', found: '1'
Test #14:
score: 0
Wrong Answer
time: 3030ms
memory: 170968kb
input:
99999 10490328589436 1000000000 13762508396295 1000000000 40632115714511 1000000000 32834989282081 1000000000 29091918306598 1000000000 24352818172350 1000000000 23447797352860 1000000000 38073075086135 1000000000 14288530509239 1000000000 36463049009868 1000000000 10562334120356 1000000000 34490016...
output:
1 1 99999 0 2 1 50000 700388007 4 1 25000 700388007 9 12501 25000 857403793 18 12501 18750 857403793 36 12501 15625 857403793 72 12501 14063 857403793 144 12501 13282 857403793 288 12501 12891 857403793 576 12501 12696 857403793 1152 12501 12598 857403793 2304 12501 12549 857403793 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '700388007', found: '1'
Test #15:
score: 0
Wrong Answer
time: 3142ms
memory: 170812kb
input:
99999 61585049539216 1000000000 58981995705940 1000000000 44247484521936 1000000000 70916218483207 1000000000 47696673638497 1000000000 60781033156530 1000000000 55859922511212 1000000000 59143999312357 1000000000 57175954090596 1000000000 71328224891428 1000000000 46047599292678 1000000000 47510666...
output:
1 1 99999 0 2 1 50000 656243188 4 1 25000 656243188 9 12501 25000 807266817 18 12501 18750 807266817 36 12501 15625 807266817 72 12501 14063 807266817 144 12501 13282 807266817 288 12501 12891 807266817 576 12501 12696 807266817 1152 12501 12598 807266817 2304 12501 12549 807266817 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '656243188', found: '1'
Test #16:
score: 0
Wrong Answer
time: 3088ms
memory: 171136kb
input:
99999 21219982576425 1000000000 42260400232639 1000000000 26412110792985 1000000000 11035481121988 1000000000 13219690258669 1000000000 19550933913223 1000000000 32679237390903 1000000000 15679803374289 1000000000 23896051833122 1000000000 20099950455987 1000000000 14778766729432 1000000000 21547991...
output:
1 1 99999 0 2 1 50000 123004833 4 1 25000 123004833 9 12501 25000 258879463 18 12501 18750 258879463 36 12501 15625 258879463 72 12501 14063 258879463 144 12501 13282 258879463 288 12501 12891 258879463 576 12501 12696 258879463 1152 12501 12598 258879463 2304 12501 12549 258879463 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '123004833', found: '1'
Test #17:
score: 0
Wrong Answer
time: 3109ms
memory: 170752kb
input:
99999 28503598869279 1000000000 32397709666940 1000000000 25833502058723 1000000000 38020841213328 1000000000 54560138759501 1000000000 42230929758874 1000000000 28972613620824 1000000000 28498598787317 1000000000 54070131397843 1000000000 22084267818956 1000000000 37776835952805 1000000000 44465973...
output:
1 1 99999 0 2 1 50000 809311757 4 1 25000 809311757 9 12501 25000 260618005 18 12501 18750 260618005 36 12501 15625 260618005 72 12501 14063 260618005 144 12501 13282 260618005 288 12501 12891 260618005 576 12501 12696 260618005 1152 12501 12598 260618005 2304 12501 12549 260618005 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '809311757', found: '1'
Test #18:
score: 0
Wrong Answer
time: 3082ms
memory: 170776kb
input:
99999 18175781548542 1000000000 40883228277118 1000000000 33828113807745 1000000000 17817771477758 1000000000 22749897023579 1000000000 18015777423352 1000000000 28920025506062 1000000000 18799798298070 1000000000 27979006765970 1000000000 17103749421004 1000000000 24329932307643 1000000000 29798042...
output:
1 1 99999 0 2 1 50000 0 4 1 25000 530050851 9 12501 25000 464584067 18 12501 18750 464584067 36 12501 15625 464584067 72 12501 14063 464584067 144 12501 13282 464584067 288 12501 12891 464584067 576 12501 12696 464584067 1152 12501 12598 464584067 2304 12501 12549 464584067 4608 12501 12525 46458406...
result:
wrong answer 1st numbers differ - expected: '530050851', found: '1'
Test #19:
score: 0
Wrong Answer
time: 3089ms
memory: 170952kb
input:
99999 13631696063382 1000000000 19095823575649 1000000000 18048800926387 1000000000 17060779354093 1000000000 15768748767399 1000000000 30886037572930 1000000000 26814970558482 1000000000 8165534157289 1000000000 27914989206121 1000000000 34170089895536 1000000000 27764986366439 1000000000 145187181...
output:
1 1 99999 0 2 1 50000 128224308 4 1 25000 128224308 9 12501 25000 528151600 18 12501 18750 528151600 36 12501 15625 528151600 72 12501 14063 528151600 144 12501 13282 528151600 288 12501 12891 528151600 576 12501 12696 528151600 1152 12501 12598 528151600 2304 12501 12549 528151600 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '128224308', found: '1'
Test #20:
score: 0
Wrong Answer
time: 3077ms
memory: 170904kb
input:
99999 71091006018203 1000000000 42267334298998 1000000000 53421686894439 1000000000 52992676205010 1000000000 49055576058012 1000000000 70721000416119 1000000000 43151374327143 1000000000 70716000332404 1000000000 51528640431406 1000000000 65945925001029 1000000000 39524135856472 1000000000 66414932...
output:
1 1 99999 0 2 1 50000 961356073 4 1 25000 961356073 9 12501 25000 420404947 18 12501 18750 420404947 36 12501 15625 420404947 72 12501 14063 420404947 144 12501 13282 420404947 288 12501 12891 420404947 576 12501 12696 420404947 1152 12501 12598 420404947 2304 12501 12549 420404947 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '961356073', found: '1'
Test #21:
score: 0
Wrong Answer
time: 3076ms
memory: 170852kb
input:
99999 43981987091230 1000000000 41793950053258 1000000000 23385527966154 1000000000 32049759202175 1000000000 48927065970165 1000000000 26694629471843 1000000000 27661655640242 1000000000 37241867113918 1000000000 49110069037684 1000000000 20323405372655 1000000000 43304975621086 1000000000 48021052...
output:
1 1 99999 0 2 1 50000 92516536 4 1 25000 92516536 9 12501 25000 814929516 18 12501 18750 814929516 36 12501 15625 814929516 72 12501 14063 814929516 144 12501 13282 814929516 288 12501 12891 814929516 576 12501 12696 814929516 1152 12501 12598 814929516 2304 12501 12549 814929516 4608 12501 12525 81...
result:
wrong answer 1st numbers differ - expected: '92516536', found: '1'
Test #22:
score: 0
Wrong Answer
time: 2986ms
memory: 170916kb
input:
99999 31159466866911 1000000000 28413414847308 1000000000 25948364344910 1000000000 31236468095715 1000000000 22036273821032 1000000000 24056321657736 1000000000 36031551606814 1000000000 37935581367999 1000000000 40624624246259 1000000000 18857191994835 1000000000 22179277697755 1000000000 29154428...
output:
1 1 99999 0 2 1 50000 733458470 4 1 25000 733458470 9 12501 25000 765924234 18 12501 18750 765924234 36 12501 15625 765924234 72 12501 14063 765924234 144 12501 13282 765924234 288 12501 12891 765924234 576 12501 12696 765924234 1152 12501 12598 765924234 2304 12501 12549 765924234 4608 12501 12525 ...
result:
wrong answer 1st numbers differ - expected: '733458470', found: '1'