QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99400#6327. Count Arithmetic ProgressionyangjlML 3ms9476kbC++202.8kb2023-04-22 11:17:012023-04-22 11:17:02

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 11:17:02]
  • 评测
  • 测评结果:ML
  • 用时:3ms
  • 内存:9476kb
  • [2023-04-22 11:17:01]
  • 提交

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 {
        return (b-it.b)/(it.k-k)+((b-it.b)%(it.k-k)!=0);
    }
    ll get(ll x) const{
        return k*x+b;
    }
    friend ostream& operator<<(ostream& out,const Line& a) {
        return out<<"["<<a.k<<" "<<a.b<<"]";
    }
};
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;
    // debug(a1);
    // debug(a2);
    // debug(xl,xr);
    // k1*x+b1 <= A0 <= k2*x+b2
    bool left=(a1.get(xl)<=a2.get(xl));
    bool right=(a1.get(xr)<=a2.get(xr));
    // debug(left,right);
    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);
    ans+=max(0ll,a2.get(xm)-a1.get(xm)+1);
    solve(a1,a2,xl,xm-1);
    solve(a1,a2,xm+1,xr);
}

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 && st1[n1].cross(a)<=st1[n1].cross(st1[n1-1])) {
            // 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 && st2[n2].cross(a)<=st2[n2].cross(st2[n2-1]))
            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);
        debug(st1[n1],st2[n2]);
        debug(xl,x);
        debug(ans);
        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: 3ms
memory: 9476kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 3ms
memory: 9476kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Memory Limit Exceeded

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:


result: