QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99654 | #6327. Count Arithmetic Progression | yangjl | WA | 84ms | 21780kb | C++20 | 3.4kb | 2023-04-23 11:55:03 | 2023-04-23 11:55:05 |
Judging History
answer
#include<iostream>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
#include<bitset>
#include<climits>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
struct ConvexHull {
// 单调栈维护凸包
// 插入直线:求最大值时,斜率递增插入,求最小值时,斜率递减插入
// 对x询问:横坐标递减询问
using T=long long;
static constexpr T INF=T(1e12)+10;/*TODO*/
struct Line {
T k,b;
T cross(const Line& o)const {
// 交点横坐标向上取整
T ans=(b-o.b)/(o.k-k);
if((b-o.b)%(o.k-k)!=0 && ans>=0)
ans+=1;
return ans;
}
T get(T x)const {
return k*x+b;
}
friend ostream& operator<<(ostream& out,const Line& a) {
return out<<a.k<<"X+"<<a.b;
}
T areaWith(const Line& o,T xl,T xr)const {
// 返回夹在this和o之间的整点数
if(xl>xr)
return 0;
bool left=(get(xl)<=o.get(xl));
bool right=(get(xr)<=o.get(xr));
if(!left && !right)
return 0;
if(left && right)
return (o.k-k)*(xr-xl+1)*(xl+xr)/2+(o.b-b+1)*(xr-xl+1);
T xm=cross(o);
if(!left && right)
return (o.k-k)*(xr-xm+1)*(xm+xr)/2+(o.b-b+1)*(xr-xm+1);
if(get(xm)!=o.get(xm))
xm--;
return (o.k-k)*(xm-xl+1)*(xm+xl)/2+(o.b-b+1)*(xm-xl+1);
}
};
vector<Line> st;
vector<T> x;
int n;
ConvexHull(int capacity):st(capacity),x(capacity),n(-1) {}
void push(T k,T b) {
Line v{k,b};
while(n>=1 && canPop(st[n-1],st[n],v))
n--;
st[++n]=v;
x[n]=(!n ? -INF: v.cross(st[n-1]));
}
void popUtil(T p) {
while(n>0 && p<x[n])
n--;
}
Line top()const {
return st[n];
}
T topX()const {
return x[n];
}
int size()const {
return n+1;
}
private:
bool canPop(const Line& t1,const Line& t0,const Line& v) {
// t0.cross(v)<=t0.cross(t1)
T le=(t0.b-v.b)*(t1.k-t0.k);/*TODO*/
T ri=(t0.b-t1.b)*(v.k-t0.k);
bool sign=(v.k<t0.k)^(t1.k<t0.k);
return sign?le>=ri:le<=ri;
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin>>n;
vector<ll> L(n),R(n);
for(auto& x:L) cin>>x;
for(auto& x:R) cin>>x;
ConvexHull c1(n),c2(n);
for(int i=n-1; i>=0; --i)
c1.push(-i,L[i]);
for(int i=0; i<n; ++i)
c2.push(-i,R[i]);
// debug_n(c1.st,c1.size());
// debug_n(c2.st,c2.size());
ll x=ConvexHull::INF, ans=0;
while(1) {
c1.popUtil(x);
c2.popUtil(x);
ll xl=max(c1.topX(),c2.topX());
ans+=c1.top().areaWith(c2.top(),xl,x);
x=xl-1;
if(c1.size()==1 && c2.size()==1)
break;
}
cout<<ans;
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3364kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3368kb
input:
4 2 3 1 6 5 6 4 8
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 84ms
memory: 21780kb
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: -100
Wrong Answer
time: 2ms
memory: 3432kb
input:
2 1 1 1000000000000 1000000000000
output:
2003764205206896640
result:
wrong answer 1st numbers differ - expected: '276262510', found: '2003764205206896640'