QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99472#6327. Count Arithmetic ProgressionyangjlWA 69ms13752kbC++203.3kb2023-04-22 17:16:582023-04-22 17:17:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-22 17:17:00]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:13752kb
  • [2023-04-22 17:16:58]
  • 提交

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'