QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209488#6327. Count Arithmetic Progressionucup-team870Compile Error//C++143.6kb2023-10-10 15:21:292023-10-10 15:21:30

Judging History

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

  • [2023-10-10 15:21:30]
  • 评测
  • [2023-10-10 15:21:29]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define lll __int128
const int N = 300030,mod=998244353;
const ll inf=1e12+5;
int L[N], R[N];
struct node {
    int x, y;
    node (int _x = 0, int _y = 0) {x = _x, y = _y;}
} st[N], a[N], b[N];
ll operator ^ (node a, node b) {return 1ll * a.x * b.y - 1ll * b.x * a.y; }
node operator - (node a, node b) {return node(a.x-b.x, a.y-b.y);}
void build1(node *a, int &n) {
    int top = 0;
    rep (i, 1, n) {
        while (top > 1 && ((st[top] - st[top-1]) ^ (a[i] - st[top-1])) <= 0) top--;
        st[++top] = a[i];
    }
    rep (i, 1, top) a[i] = st[i];
    n = top;
}
void build2(node *a, int &n) {
    int top = 0;
    rep (i, 1, n) {
        while (top > 1 && ((st[top] - st[top-1]) ^ (a[i] - st[top-1])) >= 0) top--;
        st[++top] = a[i];
    }
    rep (i, 1, top) a[i] = st[i];
    n = top;
}
ll flr(ll x,ll y){
    if(x>=0)return x/y;
    ll v=x/y; return v-(v*y!=x);
}
struct fs{
    ll fz,fm;
    bool operator < (const fs&t)const &{
        assert(fm>0 && t.fm>0);
        return fz*t.fm<fm*t.fz;
    };
    ll fl(){
        return flr(fz,fm);
    }
    ll cl(){
        return flr(fz-1,fm);
    }
    ll cel(){
        if(fz>=0)return (fz-1)/fm+1;
        return fz/fm;
    }
};
pair<fs,int>q[N*2];
fs q1[N],q2[N];
int main() {
    int n; scanf("%d", &n);
    rep (i, 1, n) {
        scanf("%d", &L[i]);
    }
    rep (i, 1, n) {
        scanf("%d", &R[i]);
    }
    rep (i, 1, n) {
        a[i] = node(i, R[i]);
        b[i] = node(i, L[i]);
    }
    int s1 = n, s2 = n;
    build1(a, s1);
    // rep(i,1,s1)cout<<a[i].x<<' '<<a[i].y<<'\n';
    build2(b, s2);
    // rep(i,1,s2)cout<<b[i].x<<' '<<b[i].y<<'\n';
    rep(i,2,s1)q1[i]={a[i].y-a[i-1].y , a[i].x-a[i-1].x};
    rep(i,2,s1)assert(q1[i]<q1[i+1]);
    rep(i,2,s2)q2[i]={b[i].y-b[i-1].y , b[i].x-b[i-1].x};
    rep(i,2,s2)assert(q2[i]>q2[i+1]);
    int cnt=0;
    q[++cnt]={{-inf,1},0}; q[++cnt]={{inf,1},0};
    rep(i,2,s1)q[++cnt]={q1[i],1};
    rep(i,2,s2)q[++cnt]={q2[i],-1};
    sort(q+1,q+cnt+1);
    // rep(i,1,cnt){
    //     cout<<q[i].first.fz<<" "<<q[i].first.fm<<' '<<q[i].second<<'\n';
    // }
    int i1=1,i2=s2;
    auto cal=[&](ll L,ll R){
        // cout<<L<<" "<<R<<" "<<i1<<" "<<i2<< '\n';
        if(L>R)return 0ll;
        ll k1=-a[i1].x,b1=a[i1].y; ll k2=-b[i2].x,b2=b[i2].y;
        // swap(k1,k2); swap(b1,b2);
        // cout<<i1<<' '<<i2<<" "<< L<<" "<<R<<" "<<k1<<" "<<b1<<" "<<k2<<" "<<b2<<'\n';
        lll len=R-L+1;
        if(k1==k2){
            return (ll)(len*max(0ll,b1-b2+1)%mod);
        }
        ll d=k1-k2,fz=b2-b1;
        ll l=-inf,r=inf;
        if(d<0){
            d=-d;fz=-fz; r=min(r,fs{fz,d}.fl());
        }
        else l=max(l,fs{fz,d}.cel());
        // cout<<l<<' '<<r<<'\n';
        L=max(L,l); R=min(R,r);
        if(L>R)return 0ll;
        len=R-L+1;
        return (ll)((b1-b2+1)*len+(k1-k2)*len*(L+R)/2)%mod;
    };
    ll ans=0;
    ans+=cal(q[1].first.cel(),q[2].first.cl());
    // cout<<cal(q[1].first.cel(),q[2].first.cl())<<'\n';
    assert(q[1].second==0 && q[cnt].second==0);
    rep(i,2,cnt-1){
        if(q[i].second==1)++i1;
        else --i2;
        ans=(ans+cal(q[i].first.cel(),q[i+1].first.cl()))%mod;
        // cout<<cal(q[i].first.cel(),q[i+1].first.cl())<<'\n';
    }
    cout<<ans<<'\n';
}
/*
3
5 5 2
7 6 7
*/

Details

In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
answer.code: In function ‘int main()’:
answer.code:80:28: error: no match for ‘operator>’ (operand types are ‘fs’ and ‘fs’)
   80 |     rep(i,2,s2)assert(q2[i]>q2[i+1]);
      |                       ~~~~~^~~~~~~~
      |                           |       |
      |                           fs      fs
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1132:5: note: candidate: ‘template<class _BiIter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)’
 1132 |     operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1132:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
answer.code:80:35: note:   ‘fs’ is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
   80 |     rep(i,2,s2)assert(q2[i]>q2[i+1]);
      |                                   ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1192:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)’
 1192 |     operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1192:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
answer.code:80:35: note:   ‘fs’ is not derived from ‘std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>’
   80 |     rep(i,2,s2)assert(q2[i]>q2[i+1]);
      |                                   ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1285:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’
 1285 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1285:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
answer.code:80:35: note:   ‘fs’ is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
   80 |     rep(i,2,s2)assert(q2[i]>q2[i+1]);
      |                                   ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1359:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)’
 1359 |     operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1359:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
answer.code:80:35: note:   ‘fs’ is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
   80 |     rep(i,2,s2)assert(q2[i]>q2[i+1]);
      |                                   ^
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1453:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’
 1453 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1453:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.co...