QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#97707 | #6327. Count Arithmetic Progression | whatever# | AC ✓ | 194ms | 33076kb | C++14 | 2.7kb | 2023-04-17 22:59:02 | 2023-04-17 22:59:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
using i128 = __int128_t;
using pii = pair<i64, i64>;
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int N = 300005;
const i64 inf = 1'000'000'000'005;
int n;
i64 L[N], R[N];
i128 ans;
void operator-=(pii &A, const pii &B) {
A.first -= B.first;
A.second -= B.second;
}
bool anticlock(const pii &A, pii B, pii C) {
B -= A, C -= A;
return B.first * C.second >= C.first * B.second;
}
i64 eval(const pii &A, i64 x) {
return -A.first * x + A.second;
}
vector<pii> construct(i64 *A, bool type) {
vector<pii> stk;
rep(i, 0, n - 1) {
pii cur(i, A[i]);
while ((int) stk.size() > 1 && anticlock(stk[(int) stk.size() - 2], stk.back(), cur) == type) stk.pop_back();
stk.push_back(cur);
}
return stk;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
rep(i, 0, n - 1) cin >> L[i];
rep(i, 0, n - 1) cin >> R[i];
auto HL = construct(L, true);
auto HR = construct(R, false);
vector<i64> pts;
pts.push_back(-inf), pts.push_back(inf);
rep(i, 0, (int) HL.size() - 2) {
i64 pos = (HL[i + 1].second - HL[i].second) / (HL[i + 1].first - HL[i].first);
rep(t, -1, 1) pts.push_back(pos + t);
}
rep(i, 0, (int) HR.size() - 2) {
i64 pos = (HR[i + 1].second - HR[i].second) / (HR[i + 1].first - HR[i].first);
rep(t, -1, 1) pts.push_back(pos + t);
}
sort(pts.begin(), pts.end());
pts.resize(unique(pts.begin(), pts.end()) - pts.begin());
int pl = (int) HL.size() - 1, pr = 0;
rep(i, 0, (int) pts.size() - 2) {
i64 l = pts[i], r = pts[i + 1] - 1;
while (pl > 0 && eval(HL[pl - 1], l) >= eval(HL[pl], l)) --pl;
while (pr + 1 < (int) HR.size() && eval(HR[pr + 1], l) <= eval(HR[pr], l)) ++pr;
i128 vl = eval(HR[pr], l) - eval(HL[pl], l) + 1;
i128 vr = eval(HR[pr], r) - eval(HL[pl], r) + 1;
i128 diff = HL[pl].first - HR[pr].first;
assert(vr == vl + diff * (r - l));
if (diff > 0) {
swap(vl, vr);
diff = -diff;
}
assert(vl >= vr);
if (vl <= 0) continue;
i128 len = r - l + 1;
if (vr < 0) down(len, vl / (-diff) + 1);
ans += vl * len + diff * len * (len - 1) / 2;
}
int ANS = ans % 998244353;
cout << ANS << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5444kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5452kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 68ms
memory: 8172kb
input:
300000 121398540794 60081434790 252920491076 43666218735 95583832019 21178121624 315727133812 89837170656 138389231466 174687947367 124350262341 108583578309 289629745492 321006985392 301201031648 138149017169 255983300245 138801256482 285614769875 130583757928 261690466826 74624776159 303504239011 ...
output:
2000014
result:
ok 1 number(s): "2000014"
Test #4:
score: 0
Accepted
time: 2ms
memory: 5528kb
input:
2 1 1 1000000000000 1000000000000
output:
276262510
result:
ok 1 number(s): "276262510"
Test #5:
score: 0
Accepted
time: 2ms
memory: 5464kb
input:
30 1 16647369013 21727798644 51881899844 89018646211 12783831286 65979941759 118839346175 160033057809 126387525649 99120328270 84965287126 196816164175 147276392001 80657019833 203070708878 128172816627 15790836108 155954338058 98235565946 34871844017 57611089069 112660722775 126953918553 639504624...
output:
604954208
result:
ok 1 number(s): "604954208"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5468kb
input:
296 1 700526861 4408036256 392080787 8411840609 10652071775 3362005473 15012142306 25721621405 17344573833 28155818879 29513829443 22867995239 30950458341 43328078372 1973782329 17300002611 12195468054 8193949765 23786932076 48983290670 10814466429 25194044261 14176755999 69857126392 67512072027 651...
output:
744027284
result:
ok 1 number(s): "744027284"
Test #7:
score: 0
Accepted
time: 3ms
memory: 5568kb
input:
2980 1 326425533 670465974 833387762 214047110 362391051 298281725 1412277140 722770519 958311972 2903350090 346825896 1182432466 1801573790 4107687662 1685411970 1617637530 722320994 1475561956 1516568431 6193517919 6397467313 6639037111 7603292208 7928626155 2547803566 6869005621 6985245429 914041...
output:
626349078
result:
ok 1 number(s): "626349078"
Test #8:
score: 0
Accepted
time: 6ms
memory: 6020kb
input:
29437 1 17773552 8007903 78027892 128407707 166189008 8757379 139140251 63594236 13770424 333407931 111298749 99483510 441246352 272183566 80886035 171374807 259805787 31608339 491111262 41868778 40889785 141842995 564706562 309000722 738069097 488856576 563622831 26295603 644910452 902254272 812271...
output:
328651449
result:
ok 1 number(s): "328651449"
Test #9:
score: 0
Accepted
time: 194ms
memory: 33076kb
input:
300000 1 3033799 6666601 9999834 13333023 16666168 10994290 23332323 26665334 29998301 33331223 36664101 39996935 43329724 46662468 49995168 53327824 56660435 59993002 63325524 66658002 42542881 73322825 50577776 79987470 83319725 86651937 88938754 93316226 96648304 28665032 103312327 106644272 8891...
output:
636457325
result:
ok 1 number(s): "636457325"
Test #10:
score: 0
Accepted
time: 2ms
memory: 5512kb
input:
2 528248831665 187271431213 757787259201 501127573045
output:
843443127
result:
ok 1 number(s): "843443127"
Test #11:
score: 0
Accepted
time: 3ms
memory: 5532kb
input:
29 665599460854 825216577204 139897536442 381529531264 195442556504 395731458339 216301039571 300516855397 404286093250 158586000314 126900761177 454768428040 613822875213 100555705642 269980534787 98868550313 213001687757 148337522210 263523196720 107880480566 175603102074 720677542128 42418731800 ...
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 2ms
memory: 5496kb
input:
296 30598358615 68931084514 172336289902 605841027222 927537950548 131344242165 462686184438 393771767664 22462801522 178111678126 238002566446 798938681341 97860913591 796108044351 224352270868 303055118943 364295563711 241569937767 587443755538 547171282323 203146307138 348519052830 313112432800 1...
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 3ms
memory: 5520kb
input:
2904 192568996495 108186228808 77189361769 591197727383 514969652154 14104479411 648625940 371857778568 29027258397 554306020472 2491679571 347550837550 516859380222 95166338652 321732382641 100083478427 526116293820 275155168196 282732425158 338697063545 476955983604 623770146063 255851201122 54055...
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 9ms
memory: 7788kb
input:
29889 575060103889 291646358642 190307743217 239438179683 615976000178 179191265681 553671544094 544271773737 233012221218 143925444581 91065737137 244166209142 730151013006 801609361549 291214909332 789757660943 808005531981 139290367351 135798296165 527549856423 314413412796 665375006971 187861100...
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 66ms
memory: 8044kb
input:
297259 528588711432 64699665984 115969806862 242438240991 12510623308 301760621745 738964135042 103466197201 846806768355 484509451769 88554370272 714883807013 486510503060 218275254771 444572274489 912385215847 435723678900 133772740081 184740192185 162631466771 274580397441 297211862761 4295508969...
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 3ms
memory: 5460kb
input:
30 1 2345 103 7817 3307 3358 6093 11588 12208 1535 3043 19457 257 7643 19411 7386 7393 16459 5716 4936 529 7652 1855 12852 2384 8468 6104 395 3226 1 100000 99054 96522 94799 93947 97843 91553 85213 89732 82654 81367 88574 79817 88395 83467 98333 82658 83828 85555 81014 89017 99935 89716 85650 87404 ...
output:
270038520
result:
ok 1 number(s): "270038520"
Test #17:
score: 0
Accepted
time: 3ms
memory: 5520kb
input:
294 1 119 397 1004 1330 16 468 1729 2306 658 2250 875 509 680 3670 3971 4921 5196 2253 1029 2202 6262 3751 3375 2287 3039 7522 4339 3282 5905 2941 1916 7422 7159 7419 3087 8498 2084 129 3914 8 5473 7850 62 11452 11533 7001 11223 10035 9382 2544 996 5294 7305 13273 9110 11487 10945 13936 1912 3354 10...
output:
25752294
result:
ok 1 number(s): "25752294"
Test #18:
score: 0
Accepted
time: 3ms
memory: 5584kb
input:
2961 1 26 43 38 89 56 109 81 77 62 125 268 333 127 228 503 372 118 517 151 173 523 733 194 16 516 779 57 10 737 616 1027 586 641 1123 989 50 23 182 515 25 383 87 920 87 1233 8 186 982 412 985 320 928 1350 1469 1203 88 1855 127 1462 1879 1980 953 217 1901 997 749 1949 285 766 485 2248 341 111 2382 99...
output:
2545898
result:
ok 1 number(s): "2545898"
Test #19:
score: 0
Accepted
time: 8ms
memory: 5856kb
input:
29974 1 2 4 3 11 2 21 7 27 29 31 7 40 10 23 7 10 29 23 32 53 71 53 19 40 3 75 20 48 38 58 16 87 90 8 50 21 93 82 131 27 78 115 115 124 151 26 50 33 162 137 104 101 97 165 82 181 72 110 105 114 189 148 181 136 46 123 61 184 153 162 67 160 148 234 29 253 257 136 263 266 177 100 189 22 275 20 229 211 3...
output:
253164
result:
ok 1 number(s): "253164"
Test #20:
score: 0
Accepted
time: 48ms
memory: 8356kb
input:
300000 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 1 7 8 8 8 9 9 1 10 10 10 11 11 9 12 12 12 13 3 13 14 14 14 15 15 15 16 14 16 17 17 17 18 18 4 19 19 19 20 20 20 21 21 21 22 22 22 5 23 23 10 11 24 25 25 25 7 26 12 27 27 27 28 24 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 28 34 34 34 35 35 35 36 36 25 1 3...
output:
58580
result:
ok 1 number(s): "58580"
Test #21:
score: 0
Accepted
time: 2ms
memory: 5492kb
input:
2 1 1 100000 100000
output:
17556470
result:
ok 1 number(s): "17556470"
Test #22:
score: 0
Accepted
time: 1ms
memory: 5520kb
input:
3 5035 41135 2570 47640 49552 93671
output:
358617508
result:
ok 1 number(s): "358617508"
Test #23:
score: 0
Accepted
time: 2ms
memory: 5556kb
input:
30 43558 66075 43539 29760 72314 59432 21739 22913 51195 18871 3748 19773 6350 47429 13199 36372 23216 2890 13307 2341 56493 47287 785 30384 13083 62206 46751 11396 31078 49492 66158 67057 76823 55596 93093 74366 55374 51201 80064 72803 90780 23132 52821 58473 53919 71653 99477 34261 60951 31815 885...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 2ms
memory: 5500kb
input:
291 52837 43245 38642 64765 8728 16423 43700 26401 19390 7432 73460 80305 41062 85241 1596 21614 46890 56983 11323 14491 42845 16197 14081 95955 23107 27153 40854 39540 14563 45768 29786 2847 24567 34260 17436 79672 42452 13163 54951 16926 91647 1339 68768 26886 35776 85459 16789 53851 46505 9742 58...
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 0ms
memory: 5508kb
input:
2940 1540 2221 40444 21013 6875 56348 58799 14574 11086 24292 31223 13515 14586 6446 61653 71776 5440 39761 8582 67921 54318 7257 2137 40362 42511 27134 12787 87766 69017 9937 68529 36466 12587 12086 1208 7846 38923 698 16881 53326 9880 22284 34424 28692 75816 24915 12282 7893 19272 66847 5448 60122...
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 7ms
memory: 5732kb
input:
29742 7637 10927 66951 19209 34674 10610 15751 51699 33952 51167 33358 20950 8903 11900 13558 28541 71052 65804 66979 58828 20391 22892 35471 17139 1792 44829 16393 19566 18097 45472 58095 25564 32728 37176 10824 11933 6334 40179 69919 48606 5875 29775 25957 66712 46629 46943 42431 79841 49432 2265 ...
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 53ms
memory: 8096kb
input:
299610 41887 27388 80791 45604 56719 14990 60229 36600 15138 17551 66214 59320 8845 72389 58271 23378 71393 35918 62156 74059 24566 70517 5264 2249 29621 35163 12228 14898 8385 44960 52579 29139 2395 50420 38043 31589 56708 28050 13703 35614 40749 4735 33291 25683 60204 37171 34488 9298 15348 53856 ...
output:
0
result:
ok 1 number(s): "0"