QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#824030 | #9774. Same Sum | ucup-team159# | TL | 0ms | 3712kb | C++20 | 9.5kb | 2024-12-21 11:44:49 | 2024-12-21 11:44:54 |
Judging History
你现在查看的是最新测评结果
- [2025-01-11 11:59:18]
- hack成功,自动添加数据
- (/hack/1443)
- [2024-12-23 17:02:06]
- hack成功,自动添加数据
- (/hack/1310)
- [2024-12-23 16:48:26]
- hack成功,自动添加数据
- (/hack/1309)
- [2024-12-23 16:33:45]
- hack成功,自动添加数据
- (/hack/1308)
- [2024-12-23 16:23:53]
- hack成功,自动添加数据
- (/hack/1307)
- [2024-12-23 16:13:08]
- hack成功,自动添加数据
- (/hack/1306)
- [2024-12-23 15:54:42]
- hack成功,自动添加数据
- (/hack/1305)
- [2024-12-23 14:58:39]
- hack成功,自动添加数据
- (/hack/1304)
- [2024-12-23 09:58:11]
- hack成功,自动添加数据
- (/hack/1302)
- [2024-12-23 09:47:22]
- hack成功,自动添加数据
- (/hack/1301)
- [2024-12-23 09:41:23]
- hack成功,自动添加数据
- (/hack/1300)
- [2024-12-23 09:26:32]
- hack成功,自动添加数据
- (/hack/1299)
- [2024-12-23 09:19:58]
- hack成功,自动添加数据
- (/hack/1298)
- [2024-12-23 09:13:29]
- hack成功,自动添加数据
- (/hack/1297)
- [2024-12-22 18:52:18]
- hack成功,自动添加数据
- (/hack/1296)
- [2024-12-22 18:13:14]
- hack成功,自动添加数据
- (/hack/1294)
- [2024-12-21 11:44:49]
- 提交
answer
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < (t); ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define newline puts("")
#define vc vector
using namespace std;
template<class T> using vv = vc<vc<T>>;
template<class T> using PQ = priority_queue<T,vc<T>,greater<T>>;
using uint = unsigned; using ull = unsigned long long;
using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>;
using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>; using LP = pair<ll,ll>;
int geti(){int x;scanf("%d",&x);return x;}
vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;}
template<class T1,class T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;}
template<class T1,class T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;}
template<class T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<class T>string join(const T&v,const string&d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();}
template<class T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;}
template<class T>void vin(vc<T>&a){int n;cin>>n;a=vc<T>(n);cin>>a;}
template<class T>void vin(vv<T>&a){int n,m;cin>>n>>m;a=vv<T>(n,vc<T>(m));cin>>a;}
template<class T1,class T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;}
template<class T1,class T2>void operator++(pair<T1,T2>&a,int){a.fi++;a.se++;}
template<class T>void operator--(vc<T>&a,int){for(T&x:a)x--;}
template<class T>void operator++(vc<T>&a,int){for(T&x:a)x++;}
template<class T1,class T2>void operator+=(vc<T1>&a,T2 b){for(T1&x:a)x+=b;}
template<class T1,class T2>void operator-=(vc<T1>&a,T2 b){for(T1&x:a)x-=b;}
template<class T1,class T2>void operator*=(vc<T1>&a,T2 b){for(T1&x:a)x*=b;}
template<class T1,class T2>void operator/=(vc<T1>&a,T2 b){for(T1&x:a)x/=b;}
template<class T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));}
template<class T1,class T2>pair<T1,T2>operator+(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi+b.fi,a.se+b.se};}
template<class T1,class T2>pair<T1,T2>operator-(const pair<T1,T2>&a,const pair<T1,T2>&b){return {a.fi-b.fi,a.se-b.se};}
template<class T>pair<T,T>operator*(const pair<T,T>&a,T b){return {a.fi*b,a.se*b};}
template<class T1,class T2>bool mins(T1& x,const T2&y){if(y<x){x=y;return true;}else return false;}
template<class T1,class T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;}
template<class T>T min(const vc<T>&a){return *min_element(rng(a));}
template<class T>T max(const vc<T>&a){return *max_element(rng(a));}
template<class Tx,class Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
template<class T>ll suma(const vc<T>&a){ll s=0;for(auto&&x:a)s+=x;return s;}
template<class T>ll suma(const vv<T>&a){ll s=0;for(auto&&x:a)s+=suma(x);return s;}
template<class T>void uni(T&a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
template<class T>void prepend(vc<T>&a,const T&x){a.insert(a.begin(),x);}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return;}
#define yes { puts("YES"); continue;}
#define no { puts("NO"); continue;}
#define rtn(x) { cout<<(x)<<'\n'; return;} // flush!
#define yn {puts("Yes");}else{puts("No");}
//
// Mod int
/*
const uint mod = 1000000007;/*/
const uint mod = 998244353;//*/
constexpr uint md(ll x) { x%=mod; return x<0?x+mod:x;}
constexpr ll md(ll x, ll m) { x%=m; return x<0?x+m:x;}
struct mint {
uint x;
mint(): x(0) {}
mint(ll x):x(md(x)) {}
mint operator-() const { return mint(0) - *this;}
mint operator~() const { return mint(1) / *this;}
mint& operator+=(const mint& a) { if((x+=a.x)>=mod) x-=mod; return *this;}
mint& operator-=(const mint& a) { if((x+=mod-a.x)>=mod) x-=mod; return *this;}
mint& operator*=(const mint& a) { x=(ull)x*a.x%mod; return *this;}
mint& operator/=(const mint& a) { x=(ull)x*a.pow(mod-2).x%mod; return *this;}
mint operator+(const mint& a) const { return mint(*this) += a;}
mint operator-(const mint& a) const { return mint(*this) -= a;}
mint operator*(const mint& a) const { return mint(*this) *= a;}
mint operator/(const mint& a) const { return mint(*this) /= a;}
mint pow(ll t) const {
mint res = 1; for (mint p=x;t;p*=p,t>>=1) if (t&1) res *= p; return res;
}
mint ppow(ll t) const { int p=mod-1; return pow((t%p+p)%p);}
bool operator<(const mint& a) const { return x < a.x;}
bool operator==(const mint& a) const { return x == a.x;}
bool operator!=(const mint& a) const { return x != a.x;}
};
mint ex(mint x, ll t) { return x.pow(t);}
istream& operator>>(istream&i,mint&a) {i>>a.x;return i;}
//*
ostream& operator<<(ostream&o,const mint&a) {o<<a.x;return o;}
/*/
ostream& operator<<(ostream&o, const mint&x) {
int a = x.x, b = 1;
rep(s,2)rep1(i,1000) {
int y = ((s?-x:x)*i).x; if (abs(a)+b > y+i) a = s?-y:y, b = i;
}
o<<a; if (b != 1) o<<'/'<<b; return o;
}//*/
using vm = vector<mint>;
using vvm = vector<vm>;
struct modinv {
int n; vm d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) { while (n <= i) d.pb(-d[mod%n]*(mod/n)), ++n; return d[i];}
mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
int n; vm d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) { while (n <= i) d.pb(d.back()*n), ++n; return d[i];}
mint operator[](int i) const { return d[i];}
} facs;
struct modfactinv {
int n; vm d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) { while (n <= i) d.pb(d.back()*invs(n)), ++n; return d[i];}
mint operator[](int i) const { return d[i];}
} ifacs;
mint comb(int a, int b) {
if (a < b || b < 0) return 0;
return facs(a)*ifacs(b)*ifacs(a-b);
}
struct modpow {
mint x; int n; vm d;
modpow(mint x=2, int mx=0): x(x), n(1), d(1,1) { (*this)(mx);}
mint operator()(int i) { while (n <= i) d.pb(d.back()*x), ++n; return d[i];}
mint operator[](int i) const { return d[i];}
} two(2);//, owt(invs(2));
//
const int D = 14;
// Segment tree with lazy prop
struct F {
vm d; ll s; int c;
F():d(D),s(0),c(0) {}
F(ll x):d(D),s(x),c(1) {
d[0] = 1;
rep(i,D-1) d[i+1] = d[i]*x;
}
F& operator+=(const F& f) {
rep(i,D) d[i] += f.d[i];
s += f.s; c += f.c;
return *this;
}
F operator+(const F& f) const { return F(*this) += f;}
};
ostream& operator<<(ostream&o,const F&f){return o<<f.d;}
struct G {
ll d;
G(ll d=0):d(d) {}
void operator()(F& f) const {
if (d == 0) return;
vm p(D,1);
rep(i,D-1) p[i+1] = p[i]*d;
drep(i,D) {
rep(j,i) f.d[i] += f.d[j]*p[i-j]*comb(i,j);
}
f.s += d*f.c;
}
void operator*=(const G& g) {
d += g.d;
}
};
ostream& operator<<(ostream&o,const G&g){return o<<g.d;}
// template<typename F, typename G>
struct seg {
struct FG {
F f; G g;
void apply(const G& _g) {
_g(f);
g *= _g;
}
};
vector<FG> d; int n;
seg(){}
seg(int mx) {
n = 1; while (n < mx) n <<= 1;
d = vector<FG>(n<<1);
}
int width(int i) { return 1<<(__builtin_clz(i)-__builtin_clz(n));}
void upd(int i) { d[i].f = d[i<<1].f+d[i<<1|1].f;}
FG& operator[](int i) { return d[n+i];}
void init() { drep(i,n) upd(i);}
void prop(int i) {
d[i<<1].apply(d[i].g);
d[i<<1|1].apply(d[i].g);
d[i].g = G();
}
void add(int l, int r, G g) { if (l < r) add(l,r,g,1,0,n);}
void add(int a, int b, const G& g, int i, int l, int r) {
if (a <= l && r <= b) {
d[i].apply(g);
return;
}
prop(i);
int c = (l+r)>>1;
if (a < c) add(a,b,g,i<<1,l,c);
if (c < b) add(a,b,g,i<<1|1,c,r);
upd(i);
}
void add(int v, F f, bool rpl=false) {
int i = 1;
for (int b = n; i < n; b >>= 1, i = i<<1|!!(v&b)) prop(i);
if (rpl) d[i].f = f; else d[i].f += f;
while (i > 1) i >>= 1, upd(i);
}
void set(int v, F f) { add(v,f,true);}
F get() { return d[1].f;}
F get(int l, int r) { return (l < r) ? get(l,r,1,0,n) : F();}
F get(int a, int b, int i, int l, int r) {
if (a <= l && r <= b) return d[i].f;
prop(i);
int c = (l+r)>>1;
F res;
if (a < c) res += get(a,b,i<<1,l,c);
if (c < b) res += get(a,b,i<<1|1,c,r);
return res;
}
// [segl_mxr]
};
struct Solver {
void solve() {
int n,q;
scanf("%d%d",&n,&q);
vi a(n);
cin>>a;
a *= 2;
seg t(n);
rep(i,n) t[i].f = F(a[i]);
t.init();
rep(qi,q) {
int type,l,r;
scanf("%d%d%d",&type,&l,&r);
l--;
if (type == 1) {
int c;
scanf("%d",&c);
t.add(l,r,G(c*2));
} else {
F d = t.get(l,r);
if (d.s%d.c) no;
G g(-d.s/d.c);
g(d);
bool ok = true;
for (int i = 3; i < D; i += 2) {
if (d.d[i] == 0) continue;
ok = false;
}
if (ok) yes;
no;
}
}
}
};
int main() {
// cin.tie(nullptr); ios::sync_with_stdio(false);
int ts = 1;
// scanf("%d",&ts);
rep1(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...