QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #746906 | #5657. Hungry Cow | _8_8_# | 0 | 80ms | 17936kb | C++23 | 1.4kb | 2024-11-14 15:50:14 | 2024-11-14 15:50:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e5 + 12, MOD = (int)1e9 + 7;
const ll inf = (ll)1e15;
int q;
ll d[N], b[N], s[N];
vector<ll> c;
set<pair<ll, ll>> st;
ll get(ll i) {
if(i <= 1) return 0;
i--;
return i * (i + 1) / 2;
}
map<ll, ll> f;
void test() {
cin >> q;
for(int i = 1; i <= q; i++) {
cin >> d[i] >> b[i];
c.push_back(d[i]);
st.insert({d[i], d[i]});
}
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
ll res = 0;
auto del = [&](ll l, ll r) {
res -= (get(r) - get(l));
};
auto add = [&](ll l, ll r) {
res += (get(r) - get(l));
};
for(int i = 1; i <= q; i++) {
auto it = st.lower_bound({d[i], 0});
auto [l, r] = (*it);
it = st.erase(it);
del(l, r);
ll delta = b[i] - f[d[i]];
f[d[i]] = b[i];
r += delta;
while(it != st.end() && r >= (*it).first) {
r += ((*it).second - (*it).first);
del((*it).first, (*it).second);
it = st.erase(it);
}
add(l, r);
st.insert({l, r});
cout << res << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5736kb
input:
3 4 3 1 5 1 2
output:
15 36 15
result:
wrong answer 3rd numbers differ - expected: '18', found: '15'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3628kb
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
4005 4733 7866 4161 4295 4841 6128 2631 24531
result:
wrong answer 2nd numbers differ - expected: '4656', found: '4733'
Test #3:
score: 0
Wrong Answer
time: 4ms
memory: 4064kb
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:
32605640463357510 32693975928776796 6390240475597372 6451726125508695 38685099118823012 38737448839872530 93795094996760896 93843059847892496 34989847936129844 35065127647290554 16150693162503481 16345206273851223 2530798342747941 2636625317344959 330825622744196071 330914097104207953 16800312961429...
result:
wrong answer 1st numbers differ - expected: '235118030', found: '32605640463357510'
Test #4:
score: 0
Wrong Answer
time: 80ms
memory: 17936kb
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:
125000000250000000 750000000500000000 1875000000750000000 -5723372035854775808 -3598372035604775808 8250000001500000000 -7071744071959551616 -3446744071709551616 -8545116108314327424 5303255928790448384 1204883892185672576 6829883892435672576 -5491860181023879040 -8090232217628654848 -96523221737865...
result:
wrong answer 1st numbers differ - expected: '375000007', found: '125000000250000000'
Test #5:
score: 0
Runtime Error
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:
-4936616912547215488 8073510249115120640 -7086478699286870656 -4299723573479310336 -2012968447171750016 -226213320364189696 1060541806943370624 1847296934750930944 2134052063058491264 1920807191866051584 1207562321173611904 -5682549018827776 -1718927418711267456 -3932172287903707136 -664541715659614...
result:
Test #6:
score: 0
Runtime Error
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:
-7235763922631305477 -7349377565704127194 -2437071173291263457 -1164633062023961090 -3944968956556988429 -8626883530781444167 -8923782701804847229 6159189214458550679 6709768788165072159 7247437533786159121 -6289041103017592849 -3397490786903574799 -2610626328799694484 -4994919686499497559 -64640760...
result:
Test #7:
score: 0
Runtime Error
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:
159127135708588829 -441648824545133095 3705437372528844909 -1258285609021280614 -5991013790074708215 -5873180866674704745 -3754223310442058540 -6259077483441280383 -7183935927553766881 -7495638848404380443 43923025418910383 -817550617295636719 2261764358641746167 -4386536806093623184 417512548294620...
result:
Test #8:
score: 0
Runtime Error
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:
2401207565095812697 3315805198852523838 1728486396343783955 5370795065791727165 -8965822535427132325 -7473632121541186170 9211512583987817817 -1704777779108292554 -2766932319525067442 3128351108325306684 1039224882542360748 1184382722805144138 3750743995376203167 7196331946410388623 -750069044422439...
result:
Test #9:
score: 0
Runtime Error
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:
5116745102661570966 -1889889861574449201 3624722374729041371 3543621932575574420 3530784089728972230 6064995879278438896 2808380825981908924 240402458106529636 3108620594649130227 -1167109963504561831 -658108300172800093 1232278988222882066 -3490692219950823101 -7403063475069073239 -6529175594479939...
result:
Test #10:
score: 0
Runtime Error
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:
-4764772771593461639 -5301390568656057353 -2993354417260542405 -3515787843942585634 -6821448954996538574 5357817106312431608 3983392848050371771 -1170724600985959404 182582244810971251 -3402296904129444334 -677467208660200677 -1586676241161079191 6073726141280084769 -706515300173961795 4752564955575...
result:
Test #11:
score: 0
Runtime Error
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:
-1102016845906299037 -190688495268563149 5289909220719852919 5743673868127356104 -660635915437105669 -430049465304689269 117824805161922620 1084242595334071088 4358746348056032290 5587924118168794389 7653207607670042309 8349744927458652089 7925458516808616853 -8733629935401376143 65908007430675350 1...
result:
Test #12:
score: 0
Runtime Error
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:
808978164039540500 1321995934931145391 -2526786097932844790 -758943887227066100 6605270922813196876 7357373775949922514 1479216757773603033 2134695465200942022 1274664188035716306 -6186706635070297439 -2022316817284921191 -473660134533095551 6756186219830946967 7021902165422626121 417652137262167885...
result:
Test #13:
score: 0
Runtime Error
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:
-4612916859192370133 -4228450193443778441 926021255916044299 1404814670190658489 -5606918555997646616 -4407050462258127904 -2252779085217602284 -1367031861435010937 -2598665014705113713 7537221492870098220 5729839169164047425 7435866114648914816 6297004623505958093 8152381064552162303 84870550514727...
result:
Test #14:
score: 0
Runtime Error
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:
-5368788505234869504 5591900838794400768 30420967152190720 315251844650314240 2218154202187415808 5834149255079282688 -903587607115597056 -1408269609130132480 618954541322140928 4178302721893371904 6251440878675071744 -7866685237541225984 -5407176634327690496 -4194486749843206144 -260746127745815884...
result:
Test #15:
score: 0
Runtime Error
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:
-8128922900692845824 -9097392647484137984 -5628531504343688960 -7417639674214876672 -4300803753760579840 -4789370097233154560 8115457958599328000 -6093474071432704512 -5322639938687938304 -933709509169261568 -5130996847564870912 -3553951132015057920 -3607573019633826560 -8919606484331584000 -4431397...
result:
Test #16:
score: 0
Runtime Error
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:
-2496480378339134208 -3086920608421886464 -6213641175999800576 -1385475266811666944 1712654588794600192 8821221716024663040 -8295258031655576320 -7724346396274449920 -8929460765498568448 -6206673085555054080 6441425341448877312 -87489646662185984 4913373490461672704 6889348741874019328 8954731149518...
result:
Test #17:
score: 0
Runtime Error
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:
3879275397242753280 382976865915339776 -280039641811698432 2321637770302420992 -2508572762051259136 4324001390285091840 6826054452934278912 5705247888177032192 8929765687981245696 -5501815660561590272 -7097725813223299840 -6501175166597470208 -1358229300221192448 -21680932631410688 -2022590559091378...
result:
Test #18:
score: 0
Runtime Error
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:
-2984736099263117568 2758673677870501376 43850239052837632 -1239447206874023424 -4901238549105941760 7353968861871681024 3384767346794747136 6450854306261650432 -6976511578482926848 -2858846903737274880 -3681972484135856384 -5854986091416492032 -2975534505539234048 2382140032717179392 60056643174647...
result:
Test #19:
score: 0
Runtime Error
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:
52192910141355776 3995652269255433216 3157502530959176960 1198588442123932160 -1518827181042699520 5169166358667895296 8297213703334621440 2423746338503255552 -1234203100403115264 -3237704111847483904 -101168606222665984 1529369227860212224 5661293557810577664 4995007411048440320 5393443541155687680...
result:
Test #20:
score: 0
Runtime Error
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:
-2245641874111928064 -5125387782049456128 -4709330806410936064 194522472402046976 -2845283546650475776 -6161646030571371520 -1221707294712601344 -314781456778721280 -2153919958911160576 -2838982442058187776 -352303893272525056 -2421747866013118464 -715219617343378176 -2740972103312063488 33592722196...
result:
Test #21:
score: 0
Runtime Error
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:
-3774152530925828352 -422798262415014400 -4866317572626463488 -5824943468472396288 975743218296718080 3666540403075529728 4929442117102881536 -5903100821836606976 8656584683691767040 -4973383926588889600 5993896162593467648 -7775254491578940416 -1586417866806937856 -7557373834899471360 -116766458765...
result:
Test #22:
score: 0
Runtime Error
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:
-5807245621787455232 -9101643863851719680 -5582838626836067584 -8175831739461729280 -6037806754021134592 5452950901078333952 -7433362313885523712 -7081181899078422016 7535986087843695360 -5791206482527607808 -8223257363763426048 -8373292702209755136 4378493520372205824 6670415305890756608 7335311212...