QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100056 | #6327. Count Arithmetic Progression | tikhon# | WA | 82ms | 21332kb | C++17 | 2.5kb | 2023-04-24 15:56:05 | 2023-04-24 15:56:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
// (a, b) <-> a + bx
long long upper(long long a, long long b) {
if (a >= 0)
return (a + b - 1) / b;
return -((-a) / b);
}
long long inter(const pair<long long, long long>& line1, const pair<long long, long long>& line2) {
return upper(line2.first - line1.first, line1.second - line2.second);
}
struct CHT {
vector<pair<long long, long long>> lines;
vector<long long> points;
void push_back(const pair<long long, long long>& line) {
if (lines.empty()) {
lines.emplace_back(line);
return;
}
while (!points.empty() && points.back() >= inter(lines.back(), line)) {
lines.pop_back();
points.pop_back();
}
points.emplace_back(inter(lines.back(), line));
lines.emplace_back(line);
}
};
const long long INF = 1e12 + 1e8;
const long long MOD = 998244353;
const long long half = (MOD + 1) / 2;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<long long> L(n);
vector<long long> R(n);
for (int i = 0; i < n; ++i)
cin >> L[i];
for (int i = 0; i < n; ++i)
cin >> R[i];
CHT cht1;
CHT cht2;
for (int i = 0; i < n; ++i)
cht1.push_back(make_pair(R[i] + 1, -i));
for (int i = n - 1; i >= 0; --i)
cht2.push_back(make_pair(-L[i], i));
long long cur = -INF;
int id1 = 0, id2 = 0;
long long ans = 0;
while (true) {
long long nxt = min(id1 == cht1.points.size() ? INF : cht1.points[id1],
id2 == cht2.points.size() ? INF : cht2.points[id2]);
long long a = cht1.lines[id1].first + cht2.lines[id2].first;
long long b = cht1.lines[id1].second + cht2.lines[id2].second;
long long L = cur, R = nxt;
if (b > 0)
L = max(L, upper(-a, b));
else if (b < 0)
R = min(R, upper(a, -b));
else if (a < 0)
L = R;
if (R > L)
ans = (ans + (R - L) % MOD * ((R + L - 1) % MOD) % MOD * half % MOD * (b % MOD) + (R - L) % MOD * (a % MOD))% MOD;
if (nxt == INF)
break;
if (id1 < cht1.points.size() && cht1.points[id1] == nxt)
++id1;
if (id2 < cht2.points.size() && cht2.points[id2] == nxt)
++id2;
cur = nxt;
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3480kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 82ms
memory: 7656kb
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: 3420kb
input:
2 1 1 1000000000000 1000000000000
output:
276262510
result:
ok 1 number(s): "276262510"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3432kb
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: 0ms
memory: 3364kb
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: 3472kb
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: 7ms
memory: 3772kb
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: -100
Wrong Answer
time: 81ms
memory: 21332kb
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:
-361787028
result:
wrong answer 1st numbers differ - expected: '636457325', found: '-361787028'