QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84746 | #5657. Hungry Cow | Pdw2007 | 9.090909 | 433ms | 50680kb | C++14 | 4.1kb | 2023-03-06 18:15:44 | 2023-03-06 18:15:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls k<<1
#define rs k<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
const int N=1e5+5,mod=1e9+7;
const ll inf=1e17,inv2=5e8+4;
int n,ans;
vector<pair<ll,int> > v[N<<2];
map<ll,pair<int,int> > mp;
map<ll,pair<int,int> >::iterator koishi;
void updt(int k,int l,int r,int pl,int pr,ll pos,int val) {
if(!val) return;
if(pl<=l&&r<=pr) {
v[k].push_back(make_pair(pos,val));
return;
}
int mid=(l+r)>>1;
if(mid>=pl) updt(lson,pl,pr,pos,val);
if(mid<pr) updt(rson,pl,pr,pos,val);
return;
}
int top;
vector<pair<ll,ll> > stadd[N],stdel[N];
int lstans[N];
set<pair<ll,ll> > st;
set<pair<ll,ll> >::iterator it;
int calc(ll x,ll y) {
x%=mod,y%=mod;
return 1ll*(x+y)*(y-x+1)%mod*inv2%mod;
}
void add(ll pos,int val) {
top++;
stadd[top].clear();
stdel[top].clear();
while(true) {
if(!val) break;
it=st.lower_bound(make_pair(pos,0));
if(it==st.end()) {
st.insert(make_pair(pos+val-1,pos));
stadd[top].push_back(make_pair(pos+val-1,pos));
ans+=calc(pos,pos+val-1);
if(ans>=mod) ans-=mod;
break;
}
ll r=(*it).first,l=(*it).second;
if(l>pos) {
ll t=min(l-pos,val*1ll);
if(t==l-pos) {
val-=t;
st.erase(make_pair(r,l));
stdel[top].push_back(make_pair(r,l));
ans-=calc(l,r);
if(ans<0) ans+=mod;
st.insert(make_pair(r,pos));
stadd[top].push_back(make_pair(r,pos));
ans+=calc(pos,r);
if(ans>=mod) ans-=mod;
pos=r;
continue;
}
st.insert(make_pair(pos+val-1,pos));
stadd[top].push_back(make_pair(pos+val-1,pos));
ans+=calc(pos,pos+val-1);
if(ans>=mod) ans-=mod;
break;
}
it++;
ll l2=inf,r2=inf;
if(it!=st.end()) l2=(*it).second,r2=(*it).first;
st.erase(make_pair(r,l));
stdel[top].push_back(make_pair(r,l));
ans-=(l+r)*(r-l+1)%mod*inv2%mod;
if(ans<0) ans+=mod;
ll t=min(l2-r-1,val*1ll);
if(t==l2-r-1) {
val-=t;
st.erase(make_pair(r2,l2));
stdel[top].push_back(make_pair(r2,l2));
ans-=(l2+r2)*(r2-l2+1)%mod*inv2%mod;
if(ans<0) ans+=mod;
st.insert(make_pair(r2,l));
stadd[top].push_back(make_pair(r2,l));
ans+=(l+r2)*(r2-l+1)%mod*inv2%mod;
if(ans>=mod) ans-=mod;
pos=r2;
continue;
}
st.insert(make_pair(r+val,l));
stadd[top].push_back(make_pair(r+val,l));
ans+=(l+r+val)*(r+val-l+1)%mod*inv2%mod;
if(ans>=mod) ans-=mod;
break;
}
lstans[top]=ans;
return;
}
void del(int koishi) {
while(top>koishi) {
for(int i=0;i<stdel[top].size();i++) {
st.insert(make_pair(stdel[top][i].first,stdel[top][i].second));
}
for(int i=0;i<stadd[top].size();i++) {
st.erase(make_pair(stadd[top][i].first,stadd[top][i].second));
}
top--;
ans=lstans[top];
}
return;
}
void qury(int k,int l,int r) {
int _=top;
for(int i=0;i<v[k].size();i++) add(v[k][i].first,v[k][i].second);
if(l==r) {
printf("%d\n",ans);
del(_);
return;
}
int mid=(l+r)>>1;
qury(lson);
qury(rson);
del(_);
return;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
ll x;
int y;
scanf("%lld%d",&x,&y);
if(mp.count(x)!=0) updt(1,1,n,mp[x].first,i-1,x,mp[x].second);
mp[x]=make_pair(i,y);
}
for(koishi=mp.begin();koishi!=mp.end();koishi++) {
int x=(*koishi).second.first,y=(*koishi).second.second;
updt(1,1,n,x,n,(*koishi).first,y);
}
qury(1,1,n);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.54545
Accepted
time: 1ms
memory: 17592kb
input:
3 4 3 1 5 1 2
output:
15 36 18
result:
ok 3 number(s): "15 36 18"
Test #2:
score: 4.54545
Accepted
time: 8ms
memory: 17664kb
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
4005 4656 7607 3482 3507 3753 4058 1107 24531
result:
ok 9 numbers
Test #3:
score: 0
Wrong Answer
time: 255ms
memory: 38360kb
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:
235118030 699918971 430865692 80346613 848027326 568710394 340195238 190991083 826211664 180951671 569935857 679922008 650993948 624850177 428416731 646484944 727440627 230673871 429374754 412788182 52678570 76241310 668853821 636690710 209140532 869111458 915919167 837020724 313374684 328391122 903...
result:
wrong answer 2501st numbers differ - expected: '948499983', found: '-51500024'
Test #4:
score: 0
Wrong Answer
time: 332ms
memory: 50680kb
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:
375000007 250000035 -374999916 -499999839 -1124999741 -1249999615 -1874999468 -1999999293 669968192 544968416 -80031339 -205031066 -830030772 -955030450 -1580030107 -1705029736 964937945 839938365 214938806 89939275 -535060235 -660059717 -1285059178 -1410058611 -2035058023 1134909882 509910519 38491...
result:
wrong answer 3rd numbers differ - expected: '625000091', found: '-374999916'
Test #5:
score: 0
Wrong Answer
time: 433ms
memory: 49916kb
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:
-623600028 -1247200084 -1870800168 800567009 176966869 -446633299 -1070233495 -1693833719 977533318 353933038 -269667270 -893267606 -1516867970 -2140468362 530898507 -92701941 -716302417 -1339902921 -1963503453 707863276 84262688 -539337928 -1162938572 -1786539244 884827345 261226617 -362374139 -985...
result:
wrong answer 1st numbers differ - expected: '376399979', found: '-623600028'
Test #6:
score: 0
Wrong Answer
time: 403ms
memory: 48428kb
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:
601385635 274004134 601850367 341926487 -474377322 365740738 21596345 -1140519131 -419829850 -85072718 -338283872 -90223908 -931015981 -14700446 62059976 -566762494 -977806315 -820785625 -1535566309 411107520 364298826 815707025 142534919 273592113 165836598 196695760 672590815 766944052 -53749459 6...
result:
wrong answer 5th numbers differ - expected: '525622685', found: '-474377322'
Test #7:
score: 0
Wrong Answer
time: 398ms
memory: 47860kb
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:
-194591739 531436018 575810846 354089953 -118717916 197012156 -457007199 -669962300 67690876 -633190964 -1394576200 -1695645999 938622567 994214121 883088769 637792732 72736455 167381158 300994871 217234511 -587404040 387031489 234449671 473958880 549943224 365775057 628607217 299614217 207672621 86...
result:
wrong answer 1st numbers differ - expected: '805408268', found: '-194591739'
Test #8:
score: 0
Wrong Answer
time: 370ms
memory: 47628kb
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:
201835835 176681780 819965610 401968614 20890476 624221975 244624530 -360878011 -177883159 14404016 -5966895 -539127410 65150286 -671668340 -159078858 115160143 -636536358 -667844976 -1214674111 -283015272 408770118 205347955 98965262 -377534939 -289906555 22710273 62684742 300950961 746815491 37784...
result:
wrong answer 8th numbers differ - expected: '639121996', found: '-360878011'
Test #9:
score: 0
Wrong Answer
time: 371ms
memory: 47024kb
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:
-715711049 -642248912 58956281 -88278544 -414984488 -586830252 89222244 -67834583 340803186 -451560098 -968584985 -1322918284 -671126635 -820434176 -419747423 559784456 47716886 185178829 -686039237 632404446 -182159182 722506287 755937762 554122304 371267484 84515007 906979550 609105644 706788066 1...
result:
wrong answer 1st numbers differ - expected: '284288958', found: '-715711049'
Test #10:
score: 0
Wrong Answer
time: 342ms
memory: 46916kb
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:
692991104 373664255 485258530 240812376 150262690 495543044 930860978 914610240 46074322 -36054233 -451683000 -1052403143 -420800261 42702946 -775479257 -589984207 -1464586707 -1157152623 -294110360 -339302340 310757164 211383179 211616198 608018966 63331840 943411679 25124419 -251400358 149687352 -...
result:
wrong answer 10th numbers differ - expected: '963945774', found: '-36054233'
Test #11:
score: 0
Time Limit Exceeded
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:
655956691 428350171 -742607469 -511456792 -156418412 -432457247 -801206963 -393982976 849824440 787847436 -101464177 -599628735 -668915208 -452232411 -169036647 84006460 237225865 528973566 184795902 -33096746 233905583 431595409 -47144551 346107150 468885999 341154652 -276340263 186550672 393569390...
result:
Test #12:
score: 0
Time Limit Exceeded
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:
526240962 808910950 692662359 262454820 -754836822 117168887 478758834 -368550697 401982267 372835165 362321791 -81905162 11843573 961073594 276970528 233847806 663152597 680848003 830425140 856487286 289201925 609855063 287882450 857647652 279421711 263080284 -556624546 77659055 948332609 178881513...
result:
Test #13:
score: 0
Time Limit Exceeded
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:
358833000 772113982 813032842 736093155 719583791 439590358 105432500 -41941549 -336829957 -306381292 299140703 690271575 177650600 141284783 638481365 210676272 145611620 132254845 547515625 202488291 530691433 482335430 915823467 996294007 595541992 353511196 -9380729 49382231 -112324613 -83802766...
result:
Test #14:
score: 0
Time Limit Exceeded
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:
-299612000 -857711678 -1665722259 705879399 279158742 -446854397 -1027175451 -1550912791 1031189986 689907625 351582713 236626445 -326182004 -571287221 -1507876691 -2135170235 881441975 -17125574 -368550161 -677918647 -1170225089 -1741746623 -2028619388 925607088 -61834192 -621992881 -993506695 -174...
result:
Test #15:
score: 0
Time Limit Exceeded
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:
-343756819 -1310808260 -1700293660 1068766099 355633780 126516367 -328324956 -1320613378 -1996445905 727776495 534984108 -127540731 -666182765 -1098236789 -1567154008 843444907 592289869 -326924951 -594317104 -996906697 -1346680513 -1856787419 -1875133777 -1944782099 -2142005161 17696788 -561866819 ...
result:
Test #16:
score: 0
Time Limit Exceeded
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:
-876995174 -1676552865 844157745 476844593 -354318303 -890752844 -1550887859 1121227741 759566819 107359831 -259022008 -1198712129 -2109479778 922197791 57389981 -520593202 -752041405 -1062013160 -1266663433 -2142026902 373360392 12417136 -952859257 -1630276782 -2050244050 682320648 -294852970 -8524...
result:
Test #17:
score: 0
Time Limit Exceeded
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:
-190688250 -1156769321 -1669914516 738422520 -230220519 -736463297 -1030389381 -1220504142 -2137639585 283677163 -566141385 -1375944798 -2145622157 564459229 -307530964 -521812814 -1077007653 -1541519603 1045353432 247243912 219940623 -423851182 -1147351104 -1383500898 -1897653820 916833961 56708199...
result:
Test #18:
score: 0
Time Limit Exceeded
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:
-469949156 -1065885680 -1860882295 1034613784 756563502 315482836 138357510 -448807766 -494798557 -739907475 -1264868785 -1557670952 -1783123697 541583014 412491313 -236543452 -1020431263 -1057986409 -1455876780 -1762809253 -1928779088 800457835 408290234 -445737163 -500342123 -851661784 -1791329032...
result:
Test #19:
score: 0
Time Limit Exceeded
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:
-871775699 -1635869524 1053497471 598854823 358255725 96758657 -695836761 -1434537650 937354648 309760254 -593444313 -619599776 -1108657443 -2107991399 953433702 -38161041 -1018595859 -1775225149 634581245 252637665 224089050 -700827179 -1079830272 -1161738920 -2096467916 644466881 -67042756 -973709...
result:
Test #20:
score: 0
Time Limit Exceeded
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:
-38643934 -376665795 -1182309183 -1913147589 -1943149922 352369884 -265805676 -1264667399 -1745162313 1078029148 128970548 -395929029 -1039864054 -1323362022 -1907080989 888308331 704747754 126862715 -817423508 -1370856539 -2041657599 586453193 -373681278 -992697381 -1841074147 964808254 557909218 4...
result:
Test #21:
score: 0
Time Limit Exceeded
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:
-907483471 -1555808350 1044541775 731697014 272303310 -132691529 -720817778 -788790325 -1269647695 -2106260411 361481242 -3086703 -436473242 -827573599 -1046388235 -1731824410 -1893109177 707335117 690068798 -222031110 -1091029294 -1192319628 -1796153803 810126708 153646875 -550134066 -1085398404 -1...
result:
Test #22:
score: 0
Time Limit Exceeded
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:
-266541537 -1169080414 -1718223290 -1993362682 385937182 135511816 -723970314 -791687436 -1159420617 -1502460434 849709376 848325851 501152468 154497957 129716488 -121414640 -1012948545 -1149103120 -1954177259 690227546 567774492 -226172957 -593200399 -953544667 -1050150840 -1948946223 965629172 282...