QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#98939 | #6327. Count Arithmetic Progression | HOLIC | WA | 83ms | 8044kb | C++14 | 3.1kb | 2023-04-21 00:06:10 | 2023-04-21 00:06:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1009;
const int mod = 998244353;
const int inv = (mod + 1) / 2;
#define ll long long
struct CHT{
const ll inf = 0x7f7f7f7f7f7f7f7f;
struct line{
ll k, b;
line() {}
line(ll k, ll b) : k(k), b(b) {}
double intersect(line l) {return 1.0 * (l.b - b) / (k - l.k);}
ll operator () (ll x) {return k * x + b;}
};
vector<double> x;
vector<line> li;
void init(line l) {
x.push_back({-inf}); li.push_back(l);
}
void addline(line l) {
while(li.size() >= 2 && l.intersect(li[li.size() - 2]) <= x.back()) {
x.pop_back(); li.pop_back();
}
if(!li.empty()) x.push_back(l.intersect(li.back()));
li.push_back(l);
}
ll query(ll qx) {
int id = upper_bound(x.begin(), x.end(), qx) - x.begin();
return li[id - 1](qx);
}
}up, down;
//维护一次函数的最小值,即维护上凸包,插入y=kx+b时,按k的降序插入
//维护一次函数的最大值,即维护下凸包,插入y=kx+b时,按k的升序插入
int n;
ll L[N], R[N];
void work() {
cin >> n;
for(int i = 0; i < n; i ++) cin >> L[i];
for(int i = 0; i < n; i ++) cin >> R[i];
up.init({0, R[0]});
for(int i = 1; i < n; i ++) up.addline({-i, R[i]});
down.init({-(n - 1), L[n - 1]});
for(int i = n - 2; i >= 0; i --) down.addline({-i, L[i]});
vector<int> ver;
up.x.erase(up.x.begin());
down.x.erase(down.x.begin());
for(auto v : up.x) ver.push_back(ceil(v));
// for(auto v : up.x) cout << v << endl;
for(auto v : down.x) ver.push_back(ceil(v));
sort(ver.begin(), ver.end());
ver.erase(unique(ver.begin(), ver.end()), ver.end());
ll from = -1e12, ans = 0;
int upid = 0, downid = 0;
ver.push_back(1e12);
for(auto v : ver) {
ll xl = from, xr = v;
// cout <<xl << " " << xr << endl;
ll UP = -up.li[upid].k;
ll DOWN = -down.li[downid].k;
// cout << UP << " " <<DOWN << " " << R[UP] << " "<< L[DOWN] << endl;
if(UP < DOWN) {
ll x = ceil(1.0 * (R[UP] - L[DOWN]) / (UP - DOWN));
xl = max(xl, x);
}
if(UP > DOWN){
ll x = floor(1.0 * (R[UP] - L[DOWN]) / (UP - DOWN));
xr = min(xr, x + 1);
}
// cout << xl << " " << xr << endl;
if(xl < xr) {
ans = ans + (R[UP] - L[DOWN] + 1) % mod * (xr - xl) % mod;
ans %= mod;
ans = ans + DOWN * (xr - xl) % mod * inv % mod * (xr + xl - 1) % mod;
ans = ans - UP * (xr - xl) % mod * inv % mod * (xr + xl - 1) % mod;
}
while(upid < up.x.size() && ceil(up.x[upid]) == xr) upid ++;
while(downid < down.x.size() && ceil(down.x[downid]) == xr) downid ++;
from = xr;
// cout << ans <<"!!!!" << endl;
}
cout << (ans % mod + mod) % mod << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int Case = 1;
while(Case --) work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3432kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3424kb
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: 83ms
memory: 8044kb
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:
694701233
result:
wrong answer 1st numbers differ - expected: '2000014', found: '694701233'