QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99656#6327. Count Arithmetic ProgressionyangjlWA 70ms13856kbC++204.7kb2023-04-23 12:07:322023-04-23 12:07:35

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 12:07:35]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:13856kb
  • [2023-04-23 12:07:32]
  • 提交

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;
template<int P>
struct MInt {
    int x;
    MInt(): x(0){}
    MInt(ll x): x(norm(x%P)){}
    static int norm(int x) {
        if(x<0) x+=P;
        else if(x>=P) x-=P;
        return x;
    }
    MInt pow(ll b) const{
        MInt res=1,a=*this;
        for(; b; b>>=1,a*=a)
            if(b&1) res*=a;
        return res;
    }
    MInt inv() const{
        return pow(P-2);
    }
    MInt operator-() const{
        return MInt()-*this;
    }
    MInt& operator+=(const MInt& a) {
        x=norm(x+a.x);
        return *this;
    }
    MInt& operator-=(const MInt& a) {
        x=norm(x-a.x);
        return *this;
    }
    MInt& operator*=(const MInt& a) {
        x=(ll)x*a.x%P;
        return *this;
    }
    MInt& operator/=(const MInt& a) {
        return *this*=a.inv();
    }
    friend MInt operator+(MInt l,const MInt& r) {
        return l+=r;
    }
    friend MInt operator-(MInt l,const MInt& r) {
        return l-=r;
    }
    friend MInt operator*(MInt l,const MInt& r) {
        return l*=r;
    }
    friend MInt operator/(MInt l,const MInt& r) {
        return l/=r;
    }
    friend istream& operator>>(istream& is,MInt& a) {
        ll v;
        is>>v;
        a=MInt(v);
        return is;
    }
    friend ostream& operator<<(ostream& os,const MInt& a) {
        return os<<a.x;
    }
};
const int P=998244353;
using Z=MInt<P>;
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<<"]";
    }
    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];
Z ans=0;
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+=Z(a2.k-a1.k)*(xr-xl+1)*(xl+xr)/2+Z(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+=Z(a2.k-a1.k)*(xr-xm+1)*(xm+xr)/2+Z(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+=Z(a2.k-a1.k)*(xm-xl+1)*(xm+xl)/2+Z(a2.b-a1.b+1)*(xm-xl+1);
    }else {
        // (k2-k1)*x+b2-b1, x= xl ~ xm
        xm--;
        if(xl<=xm)
            ans+=Z(a2.k-a1.k)*(xm-xl+1)*(xm+xl)/2+Z(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;
}
/*




*/

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9508kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 9520kb

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: 70ms
memory: 13856kb

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:

454748731

result:

wrong answer 1st numbers differ - expected: '2000014', found: '454748731'