結果

問題 No.2197 Same Dish
ユーザー ineedyourlovepineedyourlovep
提出日時 2023-01-20 23:19:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,609 bytes
コンパイル時間 2,533 ms
コンパイル使用メモリ 216,388 KB
実行使用メモリ 16,808 KB
最終ジャッジ日時 2023-09-05 15:49:54
合計ジャッジ時間 5,325 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
16,364 KB
testcase_01 AC 36 ms
16,448 KB
testcase_02 AC 10 ms
16,264 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 37 ms
16,304 KB
testcase_06 AC 9 ms
16,760 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 35 ms
16,448 KB
testcase_10 WA -
testcase_11 AC 9 ms
16,504 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 122 ms
16,560 KB
testcase_22 AC 132 ms
16,444 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
  }
};

//UNIONFIND
template<typename T>
struct UnionFind {
  int num;
  vector<T> d;
  UnionFind(int n=0): num(n), d(n,-1) {}
  T find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    num--;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  T size(int x) { return -d[find(x)];}
  int count() { return num;}
};

// WEIGHT_UNIONFIND
template<typename T>
struct WeightUnionFind {
  vector<int> rs, ps;
  vector<T> ws;
  WeightUnionFind(int n): rs(n, 1), ps(n), ws(n, T(0)){
    iota(ps.begin(), ps.end(), 0);
  }
  int find(int x){
    if(x == ps[x]) return x;
    int t = find(ps[x]);
    ws[x] += ws[ps[x]];
    return ps[x] = t;
  }
  T weight(int x){ find(x); return ws[x];}
  bool same(int x, int y){ return find(x) == find(y);}
  void unite(int x, int y, T w){
    w += weight(x);
    w -= weight(y);
    x = find(x); y = find(y);
    if(x == y) return;
    if(rs[x] < rs[y]) swap(x, y), w = -w;
    rs[x] += rs[y];
    ps[y] = x;
    ws[y] = w;
  }
  T diff(int x, int y){ return weight(y) - weight(x);}
};


// 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);
  vector<pair<ll, ll>> p(n);
  rep(i, 0, n) {
    int l, r;
    cin >> l >> r;
    p[i] = {r, l};
    seg.apply(l, r, 1);
  }
  int flag = 1;
  rep(i, 0, 200005) {
    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;
    return 0;
  }
  sort(p.begin(), p.end());
  UnionFind<int> uf((int)n);
  mint sub = 1;
  rep(i, 0, n) {
    auto [r, l] = p[i];
    if (i && l < p[i-1].first) uf.unite(i, i-1);
  }
  mint mul = k;
  rep(i, 0, n) {
    if (i && uf.same(i, i-1)) mul -= 1;
    else mul = k;
    sub *= mul;
//    cout << mul << " " << sub << endl;
  }
  cout << mint(mod_pow(k, n)) - sub << endl;
  return 0;
}
0