QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116016 | #6327. Count Arithmetic Progression | xaphoenix | WA | 52ms | 11008kb | C++17 | 3.9kb | 2023-06-27 21:59:03 | 2023-06-27 21:59:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LC k << 1
#define RC k << 1 | 1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = n - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, LL> pii;
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int N = 310000;
const int M = 610000;
const int mod = 998244353;
const int inf = (int)1e9;
const LL INF = (LL)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
inline int dcmp(double x) {
return (x > eps) - (x < -eps);
}
struct Point {
double x, y;
Point (double x = 0 , double y = 0) : x(x) , y(y) {}
void input() {
scanf("%lf%lf",&x,&y);
}
bool operator < (const Point& R) const {
if (dcmp(x - R.x) == 0)
return dcmp(y - R.y) < 0;
return dcmp(x - R.x) < 0;
}
bool operator == (const Point& R) const {
return dcmp(x - R.x) == 0 && dcmp(y - R.y) == 0;
}
Point operator + (const Point& R) const {
return Point(x + R.x, y + R.y);
}
Point operator - (const Point& R) const {
return Point(x - R.x, y - R.y);
}
Point operator * (const double& R) const {
return Point(x * R, y * R);
}
Point operator / (const double& R) const {
return Point(x / R, y / R);
}
double operator ^ (const Point& R) const {
return x * R.y - y * R.x;
}
double operator % (const Point& R) const {
return x * R.x + y * R.y;
}
double len() {
return sqrt(*this % *this);
}
double angle() {
return atan2(y, x);
}
};
int n, tp[2];
LL l[2][N];
pii h[2][N];
vector<LL> pos;
bool check(pii a, pii b, pii c, int k) {
pii d; d.fi = b.fi - a.fi; d.se = b.se - a.se;
return (- d.se * c.fi + d.fi * c.se <= - d.se * b.fi + d.fi * b.se) == k;
}
__int128 eval(pii a, LL x) {
__int128 cur = x;
cur *= -a.fi; cur += a.se;
return cur;
}
int main()
{
IO;
cin >> n;
rep(t, 0, 2) rep(i, 0, n) {
cin >> l[t][i];
pii cur; cur.fi = i; cur.se = l[t][i];
while (tp[t] > 1 && check(h[t][tp[t] - 1], h[t][tp[t]], cur, t)) tp[t] --;
h[t][++ tp[t]] = cur;
}
rep(t, 0, 2) {
rep(i, 1, tp[t]) {
LL x = (h[t][i].se - h[t][i + 1].se) / (h[t][i].fi - h[t][i + 1].fi);
pos.pb(x); pos.pb(x + 1); pos.pb(x - 1);
}
}
sort(all(pos));
pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
//for (auto x : pos) cout << x << " ";
//cout << "\n";
__int128 ans = 0;
int p0 = tp[0], p1 = 1;
rep(i, 0, pos.size() - 1) {
int l = pos[i], r = pos[i + 1] - 1;
while (p0 > 1 && eval(h[0][p0 - 1], l) >= eval(h[0][p0], l)) p0 --;
while (p1 < tp[1] && eval(h[1][p1 + 1], l) <= eval(h[1][p1], l)) p1 ++;
__int128 v1 = eval(h[1][p1], l) - eval(h[0][p0], l) + 1;
__int128 v2 = eval(h[1][p1], r) - eval(h[0][p0], r) + 1;
__int128 del = h[0][p0].fi - h[1][p1].fi;
if (del > 0) {
swap(v1, v2);
del = -del;
}
if (v1 <= 0) continue;
__int128 len = r - l + 1;
if (v2 < 0) down(len, v1 / (-del) + 1);
ans += v1 * len + del * len * (len - 1) / 2; ans %= mod;
/*
if (del > 0) {
swap(v1, v2); del = - del;
}
__int128 len = r - l + 1;
if (v1 <= 0) continue;
if (v2 < 0) {
v2 = v1 % (- del);
len = (v1 - v2) / (-del) + 1;
}
ans += (v1 + v2) * len / 2; ans %= mod;
*/
}
int res = ans;
cout << res << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9560kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9668kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 52ms
memory: 11008kb
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:
-524770130
result:
wrong answer 1st numbers differ - expected: '2000014', found: '-524770130'