QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99654#6327. Count Arithmetic ProgressionyangjlWA 84ms21780kbC++203.4kb2023-04-23 11:55:032023-04-23 11:55:05

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-23 11:55:05]
  • 评测
  • 测评结果:WA
  • 用时:84ms
  • 内存:21780kb
  • [2023-04-23 11:55:03]
  • 提交

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'