QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#306453 | #7782. Ursa Minor | ExplodingKonjac | WA | 1429ms | 380496kb | C++20 | 10.0kb | 2024-01-16 19:41:22 | 2024-01-16 19:41:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<16;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
};
class FastOutput final: public FastIOBase
{
public:
FastOutput(FILE *f=stdout): FastIOBase(f) {}
#ifdef OPENIOBUF
~FastOutput() { flush(); }
void flush() { fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
void put(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE) flush();
#else
putc(x,target);
#endif
}
FastOutput &operator <<(char x)
{ return put(x),*this; }
FastOutput &operator <<(const char *s)
{ for(;*s;put(*(s++)));return *this; }
FastOutput &operator <<(const std::string &s)
{ return (*this)<<s.c_str(); }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastOutput&> operator <<(T x)
{
if(x<0) return put('-'),(*this)<<(-x);
char stk[std::numeric_limits<T>::digits10+1],*top=stk;
do *(top++)=x%10+'0',x/=10; while(x);
while(top!=stk) put(*(--top));
return *this;
}
template<typename ...T>
void writesp(T &&...x)
{ std::initializer_list<int>{((*this)<<(x),put(' '),0)...}; }
template<typename ...T>
void writeln(T &&...x)
{ std::initializer_list<int>{((*this)<<(x),put('\n'),0)...}; }
template<typename Iter>
std::enable_if_t<std::is_base_of<
std::forward_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category>
::value> writesp(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<' '; }
template<typename Iter>
std::enable_if_t<std::is_base_of<
std::forward_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category>
::value> writeln(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<'\n'; }
}qout;
class FastInput final: public FastIOBase
{
private:
bool __eof;
public:
FastInput(FILE *f=stdin): FastIOBase(f),__eof(false)
#ifdef OPENIOBUF
{ buf_p=BUFSIZE; }
void flush() { buf[fread(buf,1,BUFSIZE,target)]=EOF,buf_p=0; }
bool eof()const { return buf[buf_p]==EOF; }
#else
{}
bool eof()const { return feof(target); }
#endif
char get()
{
if(__eof) return EOF;
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
char ch=buf[buf_p++];
#else
char ch=getc(target);
#endif
return ~ch?ch:(__eof=true,EOF);
}
void unget(char c)
{
__eof=false;
#ifdef OPENIOBUF
buf[--buf_p]=c;
#else
ungetc(c,target);
#endif
}
explicit operator bool()const { return !__eof; }
FastInput &operator >>(char &x)
{ while(isspace(x=get()));return *this; }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastInput&> operator >>(T &x)
{
char ch,sym=0;x=0;
while(isspace(ch=get()));
if(__eof) return *this;
if(ch=='-') sym=1,ch=get();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=get());
return unget(ch),sym?x=-x:x,*this;
}
FastInput &operator >>(char *s)
{
while(isspace(*s=get()));
if(__eof) return *this;
for(;!isspace(*s) && !__eof;*(++s)=get());
return unget(*s),*s='\0',*this;
}
FastInput &operator >>(std::string &s)
{
char str_buf[(1<<8)+1]={0},*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=get()));
if(__eof) return *this;
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=get()) && !__eof;p++);
if(p!=buf_end) break;
s.append(str_buf);
}
unget(*p),*p='\0',s.append(str_buf);
return *this;
}
template<typename ...T>
void read(T &&...x)
{ std::initializer_list<int>{((*this)>>(x),0)...}; }
template<typename Iter>
std::enable_if_t<std::is_base_of<
std::forward_iterator_tag,
typename std::iterator_traits<Iter>::iterator_category>
::value> read(Iter begin,Iter end)
{ while(begin!=end) (*this)>>*(begin++); }
}qin;
} // namespace FastIO
using FastIO::qin,FastIO::qout;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#define LOG(...) [](auto...){}(__VA_ARGS__)
#else
#define FILEIO(file)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace Math
{
template<typename Derived>
class ModintBase
{
#define DEF_OP1(op,expr) \
friend constexpr Derived operator op(const Derived &lhs,const Derived &rhs) \
{ return Derived(lhs)op##=rhs; } \
constexpr Derived &operator op##=(const Derived &rhs) \
{ return (expr),*static_cast<Derived*>(this); }
#define DEF_OP2(op,expr) \
constexpr Derived operator op(int) \
{ Derived res(*static_cast<Derived*>(this)); return op(*this),res; } \
constexpr Derived &operator op() \
{ return (expr),*static_cast<Derived*>(this); }
#define DEF_OP3(op,expr) \
constexpr Derived operator op()const \
{ return (expr); }
#define DEF_OP4(op) \
friend constexpr bool operator op(const Derived &lhs,const Derived &rhs) \
{ return lhs.val op rhs.val; }
#define MOD Derived::getMod()
protected:
int val;
private:
template<typename T>
static constexpr std::enable_if_t<std::is_integral<T>::value,T> __inv(T a,T b)
{ T x=0,y=1,t=0;for(;a;t=b/a,std::swap(a,b-=t*a),std::swap(y,x-=t*y));return x; }
template<typename T>
static constexpr std::enable_if_t<std::is_integral<T>::value,T> __fix(T x)
{ return Derived::fix(x); }
static constexpr void __qmo(int &x)
{ x+=(x>>31&MOD); }
public:
constexpr ModintBase(): val(0) {}
constexpr ModintBase(const Derived &x): val(x.val) {}
template<typename T>
constexpr ModintBase(T x): val(__fix(x)) {}
constexpr static Derived unfixed(int x)
{ return reinterpret_cast<Derived&>(x); }
constexpr Derived inv()const
{ return Derived(__inv(val,MOD)); }
constexpr int operator ()()const
{ return val; }
DEF_OP1(+,__qmo(val+=rhs.val-MOD))
DEF_OP1(-,__qmo(val-=rhs.val))
DEF_OP1(*,(val=__fix(1ll*val*rhs.val)))
DEF_OP1(/,(val=__fix(1ll*val*__inv(rhs.val,MOD))))
DEF_OP2(++,__qmo(val+=1-MOD))
DEF_OP2(--,__qmo(--val))
DEF_OP3(+,*this)
DEF_OP3(-,unfixed(val?MOD-val:0))
DEF_OP4(==) DEF_OP4(!=) DEF_OP4(<) DEF_OP4(>) DEF_OP4(<=) DEF_OP4(>=)
#undef DEF_OP1
#undef DEF_OP2
#undef DEF_OP3
#undef DEF_OP4
#undef MOD
};
template<typename T,typename U>
constexpr std::enable_if_t<std::is_integral<T>::value,U> qpow(U x,T y)
{ U res(1);for(;y;x*=x,y>>=1)if(y&1)res*=x;return res; }
class FastMod
{
private:
using ULL=uint64_t;
using U128=__uint128_t;
ULL p,m;
public:
constexpr FastMod(): p(0),m(0) {}
constexpr FastMod(ULL p): p(p),m((U128(1)<<64)/p) {}
constexpr ULL getp()const { return p; }
constexpr ULL operator()(ULL a)const
{ ULL q=(U128(m)*a)>>64,r=a-q*p;return r>=p?r-p:r; }
};
// Modint for dynamic MOD
class DModint: public ModintBase<DModint>
{
private:
using BaseT=ModintBase<DModint>;
static FastMod R;
friend BaseT;
template<typename T> static constexpr T fix(T x)
{ return x<0?R.getp()-R(-x):R(x); }
public:
using BaseT::BaseT;
static constexpr void setMod(int mod) { R=FastMod(mod); }
static constexpr int getMod() { return R.getp(); }
};
FastMod DModint::R{};
// Modint for static MOD
template<int MOD>
class SModint: public ModintBase<SModint<MOD>>
{
private:
using BaseT=ModintBase<SModint<MOD>>;
friend BaseT;
template<typename T> static constexpr T fix(T x)
{ return (x%=MOD)<0?x+MOD:x; }
public:
using BaseT::BaseT;
static constexpr int getMod() { return MOD; }
};
} // namespace Math
constexpr int MOD=1e9+9;
using Mint=Math::SModint<MOD>;
constexpr int MAXN=2e5;
constexpr Mint BASE(20070724);
int n,m,q,B,a[MAXN+5],b[MAXN+5];
Mint pw[MAXN+5],ipw[MAXN+5],sum[MAXN+5];
int f[20][MAXN+5];
inline void buildST()
{
for(int i=1;i<=m;i++) f[0][i]=b[i];
for(int i=1;(1<<i)<=m;i++)
for(int j=1;j+(1<<i)-1<=m;j++)
f[i][j]=gcd(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
inline int query(int l,int r)
{
int s=__lg(r-l+1);
return gcd(f[s][l],f[s][r-(1<<s)+1]);
}
class DSBase
{
protected:
static constexpr int BW=9,B=1<<BW;
int N;
vector<Mint> s1,s2;
public:
void build(int _n)
{
int k=_n/B+1;
N=k<<BW;
s1=vector<Mint>(N,0);
s2=vector<Mint>(k,0);
}
};
/**
* @brief point modify in O(1), range sum query in O(sqrt n)
*/
class pmrsq1: public DSBase
{
public:
void modify(int p,Mint x)
{ s1[p]+=x,s2[p>>BW]+=x; }
Mint query(int p)
{
Mint res=s1[p];
while(p&(B-1)) res+=s1[--p];
for(p>>=BW;p;) res+=s2[--p];
return res;
}
Mint query(int l,int r)
{ return query(r)-query(l-1); }
}t1[1005],t2[1005];
/**
* @brief point modify in O(sqrt n), range sum query in O(1)
*/
class pmrsq2: public DSBase
{
public:
void modify(int p,Mint x)
{
const int lim=s2.size();
while(p&(B-1)) s1[p++]+=x;
for(p>>=BW;p<lim;) s2[p++]+=x;
}
Mint query(int p)
{ return s1[p]+s2[p>>BW]; }
Mint query(int l,int r)
{ return query(r)-query(l-1); }
}t3;
int main()
{
qin>>n>>m>>q,B=sqrt(n);
qin.read(a+1,a+n+1);
qin.read(b+1,b+m+1);
buildST();
pw[0]=sum[0]=1;
for(int i=1;i<=n;i++)
{
pw[i]=pw[i-1]*BASE;
ipw[i]=pw[i].inv();
sum[i]=sum[i-1]+pw[i];
}
for(int i=1;i<=B;i++) t1[i].build(n),t2[i].build(n/i);
t3.build(n);
for(int i=1;i<=n;i++)
{
for(int k=1;k<=B;k++)
{
t1[k].modify(i,pw[i%k]*a[i]);
if(i%k==0) t2[k].modify(i/k,a[i]);
}
t3.modify(i,pw[i]*a[i]);
}
while(q--)
{
char opt;
qin>>opt;
if(opt=='U')
{
int p,x;
qin>>p>>x;
Mint dt=x-a[p];
for(int k=1;k<=B;k++)
{
t1[k].modify(p,pw[p%k]*dt);
if(p%k==0) t2[k].modify(p/k,dt);
}
t3.modify(p,pw[p]*dt);
a[p]=x;
}
else
{
int l,r,s,t,k;
qin>>l>>r>>s>>t;
k=gcd(r-l+1,query(s,t));
Mint s1,s2;
int ll=(l+k-1)/k,rr=r/k;
if(k<=B) s1=t2[k].query(ll,rr);
else for(int i=ll;i<=rr;i++) s1+=a[i*k];
s1*=sum[k-1];
if(k<=B) s2=t1[k].query(l,r);
else for(int i=l;i<=r;i+=k) s2+=t3.query(l,l+k-1)*ipw[l];
qout<<(s1==s2?"Yes":"No")<<'\n';
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9812kb
input:
6 4 5 1 1 4 5 1 4 3 3 2 4 Q 1 5 1 2 Q 2 5 3 4 U 5 2 Q 1 6 1 2 Q 2 5 3 4
output:
Yes No No Yes
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 7736kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 175ms
memory: 16684kb
input:
2000 2000 200000 1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 1 2 0 0 2 2 2 1 0 1 2 1 2 0 0 1 1 1 2 0 0 2 2 2 2 0 2 0 0 2 1 2 0 0 1 2 2 1 0 2 0 0 0 1 2 2 1 2 2 0 0 1 1 1 0 0 2 0 0 1 1 0 2 2 2 1 0 0 1 0 1 2 2 2 1 1 2 2 1 2 1 0 2 2 3 1 3 2 3 1 0 1 2 0 1 1 1 0 2 2 3 2 0 3 2 3 3 1 2 3 1 2 0 1 0 3 1 0 0 2 0 1 2 1 3 2 2...
output:
Yes Yes No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No No No No No Yes No No No Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes No No Yes No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No...
result:
ok 100554 tokens
Test #4:
score: 0
Accepted
time: 52ms
memory: 23284kb
input:
1 200000 200000 998244353 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100240 tokens
Test #5:
score: 0
Accepted
time: 49ms
memory: 22736kb
input:
6 131072 200000 0 0 0 0 1000000000 1000000000 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
output:
Yes Yes Yes No No No Yes No No No No No Yes Yes No Yes No Yes Yes Yes No No No No No No No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes No No No No Yes Yes No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No Yes No No No No No No Yes Yes No Yes N...
result:
ok 100021 tokens
Test #6:
score: -100
Wrong Answer
time: 1429ms
memory: 380496kb
input:
200000 200000 200000 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877...
output:
No No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No No No No No No Yes No No No No No Yes Yes Yes No No No No No No No No Yes No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No Yes Yes Yes Yes No No No No No No No No ...
result:
wrong answer 86th words differ - expected: 'No', found: 'Yes'