#826726 (C++11) No.880 Yet Another Segment Tree Problem

提出ソース

結果

問題	No.880 Yet Another Segment Tree Problem
ユーザー	S R
提出日時	2022-12-18 20:01:45
言語	C++11 (gcc 11.4.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	9,272 bytes
コンパイル時間	2,382 ms
コンパイル使用メモリ	171,936 KB
実行使用メモリ	17,928 KB
最終ジャッジ日時	2023-10-24 03:04:08
合計ジャッジ時間	40,176 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 17,928 KB
testcase_01	AC	5 ms 4,348 KB
testcase_02	AC	6 ms 4,348 KB
testcase_03	AC	5 ms 4,348 KB
testcase_04	AC	5 ms 4,348 KB
testcase_05	AC	4 ms 4,348 KB
testcase_06	AC	3 ms 4,348 KB
testcase_07	AC	5 ms 4,348 KB
testcase_08	AC	5 ms 4,348 KB
testcase_09	AC	6 ms 4,348 KB
testcase_10	AC	5 ms 4,348 KB
testcase_11	AC	1,937 ms 13,556 KB
testcase_12	AC	1,877 ms 13,556 KB
testcase_13	AC	1,342 ms 13,556 KB
testcase_14	AC	1,863 ms 13,556 KB
testcase_15	AC	1,926 ms 13,556 KB
testcase_16	AC	2,036 ms 13,556 KB
testcase_17	AC	1,945 ms 13,556 KB
testcase_18	AC	2,015 ms 13,556 KB
testcase_19	AC	864 ms 13,556 KB
testcase_20	AC	880 ms 13,556 KB
testcase_21	AC	900 ms 13,556 KB
testcase_22	AC	857 ms 13,556 KB
testcase_23	AC	907 ms 13,556 KB
testcase_24	AC	821 ms 13,556 KB
testcase_25	AC	845 ms 13,556 KB
testcase_26	AC	862 ms 13,556 KB
testcase_27	AC	814 ms 13,556 KB
testcase_28	AC	858 ms 13,556 KB
testcase_29	AC	1,823 ms 13,556 KB
testcase_30	AC	1,887 ms 13,556 KB
testcase_31	AC	2,001 ms 13,556 KB
testcase_32	TLE	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘std::pair<bool, S> mapping(F, S)’:
main.cpp:249:1: warning: control reaches end of non-void function [-Wreturn-type]
  249 | }
      | ^
main.cpp: In function ‘F composition(F, F)’:
main.cpp:256:1: warning: control reaches end of non-void function [-Wreturn-type]
  256 | }
      | ^

ソースコード

raw source code

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define rep2(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define per(i,n) for(long long i=n-1;i>-1ll;i--)
#define per2(i,k,n) for(long long i=n-1;i>(long long)(k)-1ll;i--)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define readi(n) ll n; cin >> (n);
#define readvi(v,n) vi v(n); rep(i,(n)) cin >> (v).at(i);
#define readvi2(v,w,n) vi v(n),w(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i);
#define readvi3(v,w,x,n) vi v(n),w(n),x(n); rep(i,(n)) cin >> (v).at(i) >> (w).at(i) >> (x).at(i);
#define readvvi(v,n,m) vvi v((n),vi(m)); rep(i,(n))rep(j,(m)) cin >> (v).at(i).at(j);
#define readp(n) P n; cin >> (n).fi >> (n).se;
#define readvp(v,n) vp v(n); rep(i,(n)) cin >> (v).at(i).fi >> (v).at(i).se;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vpp=vector<PP>;
using vvpp=vector<vpp>;
using vppp=vector<PPP>;
using vvppp=vector<vppp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=(1 << 30);
const ll INF=((ll)1 << 60);
const ll Inf=((ll)1 << 40);
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<a.fi<<' '<<a.se<<'\n';}
template<class T> void outpp(T a){cout<<get<0>(a)<<' '<<get<1>(a)<<' '<<get<2>(a)<<'\n';}
template<class T> void outppp(T a){cout<<get<0>(a)<<' '<<get<1>(a)<<' '<<get<2>(a) << ' ' <<get<3>(a)<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<v[i].fi<<' '<<v[i].se<<' ';cout<<'\n';}
template<class T> void outvpp(T v){rep(i,v.size())cout<<get<0>(v[i])<<' '<<get<1>(v[i])<<' '<<get<2>(v[i])<<' ';cout<<'\n';}
template<class T> void outvppp(T v){rep(i,v.size())cout<<get<0>(v[i])<<' '<<get<1>(v[i])<<' '<<get<2>(v[i])<<' '<<get<3>(v[i])<<' ';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outvvpp(T v){rep(i,v.size())outvpp(v[i]);}
template<class T> void outvvppp(T v){rep(i,v.size())outvppp(v[i]);}
template<class T> void outpd(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outppd(T a){cout<<'('<<get<0>(a)<<','<<get<1>(a)<<','<<get<2>(a)<<')'<<'\n';}
template<class T> void outpppd(T a){cout<<'('<<get<0>(a)<<','<<get<1>(a)<<','<<get<2>(a)<<','<<get<3>(a)<<')'<<'\n';}
template<class T> void outvpd(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvppd(T v){rep(i,v.size())cout<<'('<<get<0>(v[i])<<','<<get<1>(v[i])<<','<<get<2>(v[i])<<')';cout<<'\n';}
template<class T> void outvpppd(T v){rep(i,v.size())cout<<'('<<get<0>(v[i])<<','<<get<1>(v[i])<<','<<get<2>(v[i])<<','<<get<3>(v[i])<<')';cout<<'\n';}
template<class T> void outvvpd(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outvvppd(T v){rep(i,v.size())outvpp(v[i]);}
template<class T> void outvvpppd(T v){rep(i,v.size())outvppp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> void outm(T a){cout<<a.val()<<'\n';}
template<class T> void outvm(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i].val();}cout<<'\n';}
template<class T> void outvvm(T v){rep(i,v.size())outvm(v[i]);}
template<class T> void outd(T a,ll n = 16){cout << std::fixed << std::setprecision(n) << a<<'\n';}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void posimp(T b){if(b)out("possible");else out("impossible");}
template<class T> void PosImp(T b){if(b)out("Possible");else out("Impossible");}
template<class T> void POSIMP(T b){if(b)out("POSSIBLE");else out("IMPOSSIBLE");}
template<class T> void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';}
void outs(ll a,ll b,ll i){if(a>=i-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return (a / gcd(a,b)) * b;}
ll modpow(ll a,ll b,ll modd){ll res=1;a%=modd;while(b){if(b&1)res=res*a%modd;a=a*a%modd;b>>=1;}return res;}

/*
using mint = modint998244353;
const ll mod = 998244353;
//using mint = modint1000000007;
//const ll mod = 1000000007;
using vm=vector<mint>;
using vvm=vector<vm>;
using vvvm=vector<vvm>;
using vvvvm=vector<vvvm>;
*/

template<class S, S op(S,S), S e(), class F, pair<bool,S> mapping(F,S), F composition(F,F), F id()> 
struct segtree_beats{
  vector<S> data;
  vector<F> lazy;
  ll size, M, N;
  segtree_beats(ll n){
    size = n;
    M = 64 - __builtin_clzll(size-1);
    N = (1ll << M);
    data.resize(2*N,e());
    lazy.resize(2*N,id());
  }
  void eval(ll x){
    if(lazy.at(x) == id()) return;
    pair<bool,S> y = mapping(lazy.at(x),data.at(x));
    if(y.fi){
      data.at(x) = y.se;
      if(x < N){
        lazy.at(2*x) = composition(lazy.at(x), lazy.at(2*x));
        lazy.at(2*x+1) = composition(lazy.at(x), lazy.at(2*x+1));
      }
      lazy.at(x) = id();
    }
    else{
      lazy.at(2*x) = composition(lazy.at(x), lazy.at(2*x));
      lazy.at(2*x+1) = composition(lazy.at(x), lazy.at(2*x+1));
      eval(2*x);
      eval(2*x+1);
      data.at(x) = op(data.at(2*x),data.at(2*x+1));
      lazy.at(x) = id();
    }
  }
  void evals(ll x){
    if(x > 1) evals(x/2);
    eval(x);
  }
  void cul(ll i){
    if(i == 0) return;
    if(i < N) {
      eval(2*i);
      eval(2*i+1);
      data.at(i) = op(data.at(2*i),data.at(2*i+1));
    }
    cul(i/2);
  }
  void apply_node(ll x, F f){
    evals(x);
    lazy.at(x) = f;
    eval(x);
    cul(x/2);
  }
  void set_node(ll x, S a){
    evals(x);
    data.at(x) = a;
    eval(x);
    cul(x/2);
  }
  S get_node(ll x){
    evals(x);
    return data.at(x);
  }
  void set(ll i, S x){
    assert(0 <= i && i < size);
    set_node(i+N,x);
  }
  S get(ll i){
    assert(0 <= i && i < size);
    return get_node(i+N);
  }
  S _prod(ll l, ll r, ll x){
    if(l == r) return e();
    ll k = 63-__builtin_clzll(x);
    ll ql = (x & ~(1ll << k)) << (M-k);
    ll qr = ql + (1ll << (M-k));
    if(l <= ql && qr <= r)return get_node(x);
    if(qr <= l || r <= ql)return e();
    return op(_prod(l,r,2*x),_prod(l,r,2*x+1));
  }
  void _apply(ll l, ll r, F f,ll x){
    if(l == r) return;
    ll k = 63-__builtin_clzll(x);
    ll ql = (x & ~(1ll << k)) << (M-k);
    ll qr = ql + (1ll << (M-k));
    if(l <= ql && qr <= r) apply_node(x,f);
    else if(qr <= l || r <= ql) return;
    else _apply(l,r,f,2*x),_apply(l,r,f,2*x+1);
  }
  S prod(ll l, ll r){
    assert(0 <= l && l <= r && r <= size);
    return _prod(l,r,1);
  }
  void apply(ll l, ll r, F f){
    assert(0 <= l && l <= r && r <= size);
    return _apply(l,r,f,1);
  }
};

struct S{
  ll sum,len,lcm, max;
  S(){
    sum = 0; len = 0;
    lcm = 0; max = 0;
  }
  S(ll x) {
    sum = x;
    len = 1;
    lcm = x;
    max = x;
  }
};
S e() {
  S ret;
  return ret;
}
S op(S x, S y) {
  S ret;
  if(x.len == 0 && y.len == 0) return ret;
  ret.sum = x.sum + y.sum;
  ret.len = x.len + y.len;
  ret.max = max(x.max,y.max);
  if(x.lcm > inf+1 || y.lcm > inf+1) ret.lcm = inf;
  else ret.lcm = lcm(x.lcm,y.lcm);
  chmin(ret.lcm,inf);
  return ret;
}
using F = ll;

pair<bool,S> mapping(F f, S x){
  S ret = x;
  if(x.len == 0) return {true,ret};
  if(f == 0) return {true,ret};
  if(f < 0){
    ret.sum = ret.len * (-f);
    ret.lcm = (-f);
    ret.max = (-f);
    return {true,ret};
  }
  if(f > 0){
    if(x.len == 1){
      ret.sum = gcd(ret.sum,f);
      ret.lcm = ret.sum;
      ret.max = ret.sum;
      return {true,ret};
    }
    if(f % ret.lcm != 0) return {false,ret};
    return {true,ret};
  }
}
F composition(F f, F g){
  if(g == 0) return f;
  if(f == 0) return g;
  if(f < 0) return f;
  if(f > 0 && g > 0) return gcd(f,g);
  if(f > 0 && g < 0) return -gcd(f,-g);
}
F id(){
  return 0;
}

int main(){
  ll n, q; cin >> n >> q;
  segtree_beats<S, op, e, F, mapping, composition, id> seg(n);
  rep(i,n){
    ll a; cin >> a;
    seg.set(i,S(a));
  }
  rep(_,q){
    ll t,l,r,b; cin >> t >> l >> r; l--;
    if(t < 3) cin >> b;
    if(t == 1) seg.apply(l,r,-b);
    if(t == 2) seg.apply(l,r,b);
    if(t == 3) out(seg.prod(l,r).max);
    if(t == 4) out(seg.prod(l,r).sum);
  }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード