#834513 (C++17) No.2197 Same Dish

提出ソース

結果

問題	No.2197 Same Dish
ユーザー	ineedyourlovep
提出日時	2023-01-20 22:32:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,090 bytes
コンパイル時間	2,305 ms
コンパイル使用メモリ	210,708 KB
実行使用メモリ	16,764 KB
最終ジャッジ日時	2024-06-23 10:30:11
合計ジャッジ時間	5,212 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	54 ms 16,644 KB
testcase_01	AC	54 ms 16,624 KB
testcase_02	AC	9 ms 16,576 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	54 ms 16,608 KB
testcase_06	AC	9 ms 16,620 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	54 ms 16,552 KB
testcase_10	WA	-
testcase_11	AC	9 ms 16,756 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	123 ms 16,580 KB
testcase_22	AC	151 ms 16,636 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
//const int mod = 1000000007;
const int mod = 998244353;

//MINT
struct mint {
  unsigned x;
  mint(): x(0) {}
  mint(ll x):x((x%mod+mod)%mod) {}
  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=(unsigned long long)x*a.x%mod; return *this;}
  mint& operator/=(const mint& a) { x=(unsigned long long)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 {
    if (!t) return 1;
    mint res = pow(t>>1);
    res *= res;
    return (t&1)?res*x:res;
  }
  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) { unsigned long long t; i>>t; a=mint(t); return i;}
ostream& operator<<(ostream& o, const mint& a) { return o<<a.x;}

struct S{
  ll val;
  int size;
};
using F = ll;
S op(S a, S b){ return {a.val + b.val, a.size + b.size};}
S e(){ return {0, 1};}
S mapping(F f, S x){ return {x.val + f*x.size, x.size};}
F composition(F f, F g){ return f + g;}
F id() { return 0;}

template<class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct LSEG{
  int n, size, log = 0;
  vector<S> d;
  vector<F> lz;
  LSEG(): LSEG(0) {}
  explicit LSEG(int n): LSEG(vector<S>(n, e())) {}
  explicit LSEG(const vector<S>& v): n((int)v.size()){
    while((1<<log) < n) log++;
    size = 1<<log;
    d = vector<S>(2*size, e());
    lz = vector<F>(size, id());
    for(int i = 0; i < n; i++) d[size+i] = v[i];
    for(int i = size-1; i >= 1; i--) update(i);
  }
  void update(int k){ d[k] = op(d[2*k], d[2*k+1]);}
  void all_apply(int k, F f){
    d[k] = mapping(f, d[k]);
    if(k < size) lz[k] = composition(f, lz[k]);
  }
  void push(int k){
    all_apply(2*k, lz[k]);
    all_apply(2*k+1, lz[k]);
    lz[k] = id();
  }
  void set(int p, S x){
    assert(0 <= p && p < n);
    p += size;
    for(int i = log; i >= 1; i--) push(p>>i);
    d[p] = x;
    for(int i = 1; i <= log; i++) update(p>>i);
  }
  S get(int p){
    assert(0 <= p && p < n);
    p += size;
    for(int i = log; i >= 1; i--) push(p>>i);
    return d[p];
  }
  S prod(int l, int r){
    assert(0 <= l && l <= r && r <= n);
    if(l == r) return e();
    l += size;
    r += size;
    for(int i = log; i >= 1; i--){
      if(((l>>i)<<i) != l) push(l>>i);
      if(((r>>i)<<i) != r) push((r-1)>>i);
    }
    S sml = e(), smr = e();
    while(l < r){
      if(l&1) sml = op(sml, d[l++]);
      if(r&1) smr = op(d[--r], smr);
      l >>= 1; r >>= 1;
    }
    return op(sml, smr);
  }
  S all_prod() { return d[1];}
  void apply(int p, F f){
    assert(0 <= p && p < n);
    p += size;
    for(int i = log; i >= 1; i--) push(p>>i);
    d[p] = mapping(f, d[p]);
    for(int i = 1; i <= log; i++) update(p>>i);
  }
  void apply(int l, int r, F f){
    assert(0 <= l && l <= r && r <= n);
    if(l == r) return;
    l += size; r += size;
    for(int i = log; i >= 1; i--){
      if(((l>>i)<<i) != l) push(l>>i);
      if(((r>>i)<<i) != r) push((r-1)>>i);
    }
    {
      int l2 = l, r2 = r;
      while(l < r){
        if(l&1) all_apply(l++, f);
        if(r&1) all_apply(--r, f);
        l >>= 1; r >>= 1;
      }
      l = l2; r = r2;
    }
    for(int i = 1; i <= log; i++){
      if(((l>>i)<<i) != l) update(l>>i);
      if(((r>>i)<<i) != r) update((r-1)>>i);
    }
  }
  template<bool (*g)(S)>
  int max_right(int l){return max_right(l, [](S x){ return g(x);});}
  template<class G>
  int max_right(int l, G g){
    assert(0 <= l && l <= n);
    assert(g(e()));
    if(l == n) return n;
    l += size;
    for(int i = log; i >= 1; i--) push(l>>i);
    S sm = e();
    do{
      while((l&1) == 0) l >>= 1;
      if(!g(op(sm, d[l]))){
        while(l < size){
          push(l);
          l = 2*l;
          if(g(op(sm, d[l]))){
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    }while((l&-l) != l);
    return n;
  }
  template<bool (*g)(S)>
  int min_left(int r){ return min_left(r, [](S x){ return g(x);});}
  template<class G>
  int min_left(int r, G g){
    assert(0 <= r && r <= n);
    assert(g(e()));
    if(r == 0) return 0;
    r += size;
    for(int i = log; i >= 1; i--) push((r-1)>>i);
    S sm = e();
    do{
      r--;
      while(r > 1 && (r&1)) r >>= 1;
      if(!g(op(d[r], sm))){
        while(r < size){
          push(r);
          r = 2*r + 1;
          if(g(op(d[r], sm))){
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    }while((r&-r) != r);
    return 0;
  }
};

// POWER_MODver. N^k % MOD
ll mod_pow(ll n, ll k){
  ll res = 1;
  for(; k > 0; k >>= 1){
    if(k&1) res = (res*n)%mod;
    n = (n*n)%mod;
  }
  return res;
}


int main()
{
  ll n, k;
  cin >> n >> k;
  LSEG<S, op, e, F, mapping, composition, id> seg(200005);
  rep(i, 0, n) {
    int l, r;
    cin >> l >> r;
    seg.apply(l, r, 1);
  }
  int flag = 1;
  ll mx = 0;
  rep(i, 0, 200005) {
    mx = max(mx, seg.get(i).val);
    if (seg.get(i).val >= 2) flag = 0;
    if (seg.get(i).val > k) {
      cout << mod_pow(k, n) << endl;
      return 0;
    }
  }
  if (flag) cout << 0 << endl;
  else {
    mint ans = k;
    cout << ans*mx*(mx-1)/2*mod_pow(k, n-2) << endl;
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード