QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99472 | #6327. Count Arithmetic Progression | yangjl | WA | 69ms | 13752kb | C++20 | 3.3kb | 2023-04-22 17:16:58 | 2023-04-22 17:17:00 |
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;
const ll INF=ll(1e12)+10;
struct Line {
ll k,b;
ll cross(const Line& it)const {
ll ans=(b-it.b)/(it.k-k);
if((b-it.b)%(it.k-k)!=0 && ans>=0)
ans+=1;
return ans;
}
ll get(ll x) const{
return k*x+b;
}
friend ostream& operator<<(ostream& out,const Line& a) {
return out<<"["<<a.k<<" "<<a.b<<"]";
}
friend bool canPop(const Line& a1,const Line& a2,const Line& a3) {
// a2.cross(a3)<=a2.cross(a1)
// (a2.b-a3.b)/(a3.k-a2.k)<=(a2.b-a1.b)/(a1.k-a2.k);
ll le=(a2.b-a3.b)*(a1.k-a2.k);
ll ri=(a2.b-a1.b)*(a3.k-a2.k);
bool sign=(a3.k<a2.k)^(a1.k<a2.k);
return sign?le>=ri:le<=ri;
}
};
Line st1[N],st2[N];
ll xl1[N],xl2[N],ans;
int n1=0,n2=0;
void solve(const Line& a1,const Line& a2,ll xl,ll xr) {
if(xl>xr) return;
// k1*x+b1 <= A0 <= k2*x+b2
bool left=(a1.get(xl)<=a2.get(xl));
bool right=(a1.get(xr)<=a2.get(xr));
if(!left && !right)
return;
if(left && right) {
// (k2-k1)*x+b2-b1, x= xl ~ xr
ans+=(a2.k-a1.k)*(xr-xl+1)*(xl+xr)/2+(a2.b-a1.b+1)*(xr-xl+1);
return;
}
ll xm=a1.cross(a2);
if(!left && right) {
// (k2-k1)*x+b2-b1, x= xm ~ xr
ans+=(a2.k-a1.k)*(xr-xm+1)*(xm+xr)/2+(a2.b-a1.b+1)*(xr-xm+1);
}else if(a1.get(xm)==a2.get(xm)){
// (k2-k1)*x+b2-b1, x= xl ~ xm
ans+=(a2.k-a1.k)*(xm-xl+1)*(xm+xl)/2+(a2.b-a1.b+1)*(xm-xl+1);
}else {
// (k2-k1)*x+b2-b1, x= xl ~ xm
xm--;
if(xl<=xm)
ans+=(a2.k-a1.k)*(xm-xl+1)*(xm+xl)/2+(a2.b-a1.b+1)*(xm-xl+1);
}
}
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;
for(int i=n-1; i>=0; --i) {
Line a{-i,L[i]};
while(n1>=2 && canPop(st1[n1-1],st1[n1],a)) {
// debug(st1[n1],st1[n1-1]);
// debug(st1[n1].cross(a),st1[n1].cross(st1[n1-1]));
n1--;
}
st1[++n1]=a;
if(n1==1) xl1[n1]=-INF;
else xl1[n1]=a.cross(st1[n1-1]);
}
for(int i=0; i<n; ++i) {
Line a{-i,R[i]};
while(n2>=2 && canPop(st1[n1-1],st1[n1],a))
n2--;
st2[++n2]=a;
if(n2==1) xl2[n2]=-INF;
else xl2[n2]=a.cross(st2[n2-1]);
}
debug_n(st1+1,n1);
debug_n(st2+1,n2);
// debug_n(xl1+1,n1);
// debug_n(xl2+1,n2);
ll x=INF;
while(1) {
while(n1>=2 && x<xl1[n1])
n1--;
while(n2>=2 && x<xl2[n2])
n2--;
ll xl=max(xl1[n1],xl2[n2]);
solve(st1[n1],st2[n2],xl,x);
x=xl-1;
if(n1==1 && n2==1)
break;
}
cout<<ans;
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9564kb
input:
3 5 5 2 7 6 7
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9600kb
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: 69ms
memory: 13752kb
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:
406413645667311380
result:
wrong answer 1st numbers differ - expected: '2000014', found: '406413645667311380'