QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #119770 | #5657. Hungry Cow | pandapythoner# | 9.090909 | 690ms | 411116kb | C++14 | 4.2kb | 2023-07-05 17:41:08 | 2024-07-04 00:18:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll __int128_t
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(234);
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll rv2 = (mod + 1) / 2;
struct SGT{
struct node{
typedef node* pnode;
pnode l = nullptr;
pnode r = nullptr;
ll sm = 0;
ll empty_count = 0;
ll empty_sm = 0;
ll overflow_count = 0;
void build(ll tl, ll tr, ll val){
if(val == 0){
empty_count = tr - tl + 1;
empty_sm = ((tr + tl) % mod) * ((tr - tl + 1) % mod) % mod * rv2 % mod;
sm = 0;
overflow_count = 0;
} else{
assert(tl == tr);
empty_count = 0;
empty_sm = 0;
overflow_count = (val - 1) * (tr - tl + 1);
sm = ((tr + tl) % mod) * ((tr - tl + 1) % mod) % mod * rv2 % mod;
}
}
node(ll tl, ll tr, ll val){
build(tl, tr, val);
}
void push(ll tl, ll tr){
ll tm = (tl + tr) / 2;
if(l == nullptr){
l = new node(tl, tm, 0);
}
if(r == nullptr){
r = new node(tm + 1, tr, 0);
}
}
};
typedef node* pnode;
void go_deep(pnode v, ll tl, ll tr, ll &overflow, ll &sm, ll &empty_count, ll &empty_sm){
if(v == nullptr){
if(overflow >= (tr - tl + 1)){
sm = (sm + ((tr + tl) % mod) * ((tr - tl + 1) % mod) % mod * rv2) % mod;
overflow -= (tr - tl + 1);
} else{
ll mtr = (tl + overflow - 1);
ll mtl = mtr + 1;
sm = (sm + ((mtr + tl) % mod) * ((mtr - tl + 1) % mod) % mod * rv2) % mod;
empty_sm = (empty_sm + ((tr + mtl) % mod) * ((tr - mtl + 1) % mod) % mod * rv2) % mod;
empty_count += (tr - mtl + 1);
overflow = 0;
}
return;
}
if(overflow == 0){
empty_count += v->empty_count;
empty_sm = (empty_sm + v->empty_sm) % mod;
return;
}
if(overflow >= v->empty_count){
sm = (sm + v->empty_sm) % mod;
overflow -= v->empty_count;
return;
}
ll tm = (tl + tr) / 2;
// v->push(tl, tr);
go_deep(v->l, tl, tm, overflow, sm, empty_count, empty_sm);
go_deep(v->r, tm + 1, tr, overflow, sm, empty_count, empty_sm);
}
void upd(pnode v, ll tl, ll tr){
ll tm = (tl + tr) / 2;
auto l = v->l;
auto r = v->r;
v->overflow_count = r->overflow_count;
v->sm = (l->sm + r->sm) % mod;
v->empty_sm = l->empty_sm;
v->empty_count = l->empty_count;
ll left_overflow = l->overflow_count;
go_deep(r, tm + 1, tr, left_overflow, v->sm, v->empty_count, v->empty_sm);
v->overflow_count += left_overflow;
}
ll glob_tl, glob_tr;
pnode root;
void build(ll tl, ll tr){
glob_tl = tl;
glob_tr = tr;
root = new node(tl, tr, 0);
}
void chng(pnode v, ll tl, ll tr, ll i, ll x){
if(tl == i && tr == i){
v->build(tl, tr, x);
return;
}
v->push(tl, tr);
ll tm = (tl + tr) / 2;
if(i <= tm){
chng(v->l, tl, tm, i, x);
} else{
chng(v->r, tm + 1, tr, i, x);
}
upd(v, tl, tr);
}
void chng(ll i, ll x){
chng(root, glob_tl, glob_tr, i, x);
}
long long get(){
assert(root->overflow_count == 0);
return root->sm;
}
};
SGT sgt;
int32_t main(){
if(1){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
sgt.build(1, (1ll << 50));
int n;
cin >> n;
while(n--){
long long pos, x;
cin >> pos >> x;
sgt.chng(pos, x);
cout << sgt.get() << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.54545
Accepted
time: 0ms
memory: 3580kb
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: 0ms
memory: 3852kb
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: 16ms
memory: 21180kb
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 117th numbers differ - expected: '418131836', found: '181674159'
Test #4:
score: 0
Memory Limit Exceeded
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 625000091 500000168 875000273 750000399 125000546 721 375000924 250001148 625001400 500001673 875001974 750002296 125002639 3010 375003409 250003829 625004277 500004746 875005243 750005761 125006300 6867 375007462 250008078 625008722 500009387 875010080 750010794 125011529 12292 ...
result:
Test #5:
score: 0
Wrong Answer
time: 402ms
memory: 292884kb
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:
376399979 752799930 129199846 505599741 881999608 258399440 634799251 11199027 387598782 763998509 140398201 516797872 893197515 269597123 645996710 22396262 398795793 775195296 151594764 527994211 904393630 280793014 657192377 33591705 409991012 786390291 162789535 539188758 915587953 291987113 668...
result:
wrong answer 50003rd numbers differ - expected: '374518610', found: '538195042'
Test #6:
score: 0
Wrong Answer
time: 392ms
memory: 411116kb
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 525622685 365740738 21596345 859480883 580170157 914927289 661716135 909776099 68984026 985299561 62059976 433237513 22193692 179214382 464433705 116140252 69331558 520739757 847567658 978624852 870869337 901728499 377623547 471976784 651283280 374283948 83055...
result:
wrong answer 663rd numbers differ - expected: '865370755', found: '398847435'
Test #7:
score: 0
Wrong Answer
time: 367ms
memory: 407236kb
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:
805408268 531436018 575810846 354089953 881282091 197012156 542992808 330037707 67690876 366809043 605423814 304354015 643655299 699246853 588121501 342825464 777769194 872413897 6027603 922267250 117628699 92064221 939482410 178991612 254975956 70807789 333639949 4646949 912705360 569077475 5925366...
result:
wrong answer 428th numbers differ - expected: '188386888', found: '933685387'
Test #8:
score: 0
Wrong Answer
time: 349ms
memory: 403688kb
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 639121996 822116848 14404016 994033112 460872597 65150286 328331667 840921149 115160143 363463649 332155031 785325903 716984735 408770118 205347955 98965262 622465068 710093452 22710273 62684742 300950961 746815491 377843574 921167...
result:
wrong answer 503rd numbers differ - expected: '921765418', found: '188277444'
Test #9:
score: 0
Wrong Answer
time: 333ms
memory: 399136kb
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:
284288958 357751095 58956281 911721463 585015519 413169755 89222244 932165424 340803186 548439909 31415022 677081730 328873372 179565831 580252584 559784456 47716886 185178829 313960770 337437178 522873557 427539019 460970494 259155036 76300216 789547746 612012282 314138376 411820798 717711891 79388...
result:
wrong answer 322nd numbers differ - expected: '756079234', found: '886932940'
Test #10:
score: 0
Wrong Answer
time: 342ms
memory: 392932kb
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 963945774 548317007 947596871 579199746 42702946 224520750 410015800 535413307 842847391 705889647 660697667 310757164 211383179 211616198 608018966 63331840 943411679 25124419 748599649 149687352 404515279 1784...
result:
wrong answer 211th numbers differ - expected: '949576947', found: '854792503'
Test #11:
score: 0
Wrong Answer
time: 312ms
memory: 327380kb
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 548564542 779715219 957292615 681253780 867332278 274556258 395033249 333056245 701438428 203273870 489695476 706378273 144580619 397623726 228895978 520643679 706764212 488871564 217475631 415165457 434314301 827566002 256029845 128298498 8136098 471027033 112802895 977816195 81...
result:
wrong answer 337th numbers differ - expected: '894315783', found: '179673033'
Test #12:
score: 0
Wrong Answer
time: 292ms
memory: 312552kb
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 824971927 696977629 511671627 304096025 488742915 459595813 852048508 407821555 986580341 935810355 447338247 404215525 304626541 322321947 109610273 135672419 575250508 895903646 120155775 689920977 344461186 328119759 176168052 810451653 44880448 275429359 8...
result:
wrong answer 535th numbers differ - expected: '585370940', found: '432258530'
Test #13:
score: 0
Wrong Answer
time: 265ms
memory: 301280kb
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 63285979 813032842 736093155 525127433 245134000 66495264 919121222 462185849 492634514 674820800 65951665 846808145 101614325 851611097 714978008 763173865 749817090 98969566 753942239 795699176 747343173 205025620 285496160 869383022 627352226 630521000 689283960 597006790 625528637 3140...
result:
wrong answer 183rd numbers differ - expected: '141781984', found: '131029399'
Test #14:
score: 0
Wrong Answer
time: 645ms
memory: 284164kb
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:
700388007 142288329 334277755 410912131 984191481 258178342 677857295 154119955 441255450 99973089 761648184 646691916 83883467 838778257 902188794 274895250 996540178 97972629 746548049 437179563 944873128 373351594 86478829 745738023 758296750 198138061 826624254 77162373 383588308 924776713 31294...
result:
wrong answer 33334th numbers differ - expected: '814435540', found: '851092431'
Test #15:
score: 0
Wrong Answer
time: 690ms
memory: 283760kb
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:
656243188 689191754 299706354 773798831 60666512 831549106 376707783 384419368 708586848 137841959 945049579 282524740 743882713 311828689 842911477 958543110 707388072 788173259 520781106 118191513 768417704 258310798 239964440 170316118 973093063 837827730 258264123 566018125 921479532 10650495 36...
result:
wrong answer 33334th numbers differ - expected: '830951131', found: '554988174'
Test #16:
score: 0
Wrong Answer
time: 627ms
memory: 283780kb
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:
123004833 323447149 549190477 181877325 350714436 814279902 154144887 531293205 169632283 517425302 151043463 211353349 300585707 37295987 172488184 594505008 363056805 53085050 848434784 973071322 193491327 832548078 867271692 189854167 769886906 207484315 230310704 672685614 790862183 585017360 16...
result:
wrong answer 33334th numbers differ - expected: '551611925', found: '414439981'
Test #17:
score: 0
Wrong Answer
time: 654ms
memory: 283984kb
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:
809311757 843230693 330085498 443455252 474812220 968569449 674643365 484528604 567393168 693742634 843924093 34120680 264443328 679557432 807567246 593285396 38090557 573578614 865484367 67374847 40071558 396279760 672779845 436630051 922477136 441997628 92245661 510321866 234415732 958865087 95651...
result:
wrong answer 33334th numbers differ - expected: '965174716', found: '150746209'
Test #18:
score: 0
Wrong Answer
time: 641ms
memory: 284204kb
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:
530050851 934114334 139117719 739646516 461596234 20515568 843390249 256224973 210234182 965125271 440163961 147361794 921909056 951648485 822556784 173522019 389634215 352079069 954188705 647256232 481286397 915556038 523388437 669361047 614756087 263436426 323769185 444093816 222042331 122447902 7...
result:
wrong answer 33334th numbers differ - expected: '765070209', found: '959184952'
Test #19:
score: 0
Wrong Answer
time: 678ms
memory: 283888kb
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:
128224308 364130490 758530203 303887555 63288457 801791396 9195978 270495096 347420112 719825725 816621165 790465702 301408035 302074086 68531898 76937162 96502351 339873068 454712180 72768600 44219985 119303763 740300677 658392029 723663040 169630548 458120918 551454608 724792283 752727170 98550141...
result:
wrong answer 33334th numbers differ - expected: '327396509', found: '354340790'
Test #20:
score: 0
Wrong Answer
time: 684ms
memory: 284152kb
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:
961356073 623334212 817690831 86852425 56850092 57402616 439227063 440365347 959870440 488094612 539036019 14136442 370201424 86703456 502984496 3406527 819845957 241960918 297674702 744241678 73440618 406584128 446449664 827433568 979056809 489971921 83072885 941358982 121188376 450653101 757125941...
result:
wrong answer 33334th numbers differ - expected: '660523727', found: '469688925'
Test #21:
score: 0
Wrong Answer
time: 666ms
memory: 283928kb
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:
92516536 444191664 749574507 436729746 977336049 572341210 984214968 916242421 435385051 598772342 771546713 406978768 973592236 582491879 363677243 678241075 516956308 822433320 805167001 893067100 24068916 922778589 318944414 630257643 973777817 269996876 734732545 161430235 778275261 602052056 56...
result:
wrong answer 33334th numbers differ - expected: '314260440', found: '621555140'
Test #22:
score: 0
Wrong Answer
time: 631ms
memory: 284152kb
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:
733458470 830919600 281776724 6637332 90969914 840544555 981062432 913345310 545612129 202572312 259774840 258391315 911217939 564563428 539781959 288650831 397116933 260962358 455888226 805325749 682872695 888925253 521897811 161553543 64947370 166151994 785760107 848334640 927724641 70264903 97223...
result:
wrong answer 33334th numbers differ - expected: '425193449', found: '895673502'