結果

問題 No.3366 Reversible Tile:Revival
コンテスト
ユーザー areik
提出日時 2025-11-17 23:55:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,512 bytes
コンパイル時間 4,028 ms
コンパイル使用メモリ 260,204 KB
実行使用メモリ 11,140 KB
最終ジャッジ日時 2025-11-17 23:55:58
合計ジャッジ時間 11,931 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 24 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

using isize = size_t;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = long double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  _main();
}

void _main() {
  i64 n, m;
  cin >> n >> m;
  vector<i64> vs = {0, n};
  vector<p2> lr(m);
  for (i64 i = 0; i < m; i++) {
    i64 l, r;
    cin >> l >> r;
    l--;
    vs.push_back(l), vs.push_back(r);
    lr[i] = {l, r};
  }
  sort(vs.begin(), vs.end());
  vs.erase(unique(vs.begin(), vs.end()), vs.end());
  vector<i64> imos(vs.size());
  for (auto [l, r] : lr) {
    i64 li = lower_bound(vs.begin(), vs.end(), l) - vs.begin();
    i64 ri = lower_bound(vs.begin(), vs.end(), r) - vs.begin();
    imos[li]++, imos[ri]--;
  }
  for (i64 i = 1; i < vs.size(); i++) imos[i] += imos[i - 1];
  mint ans = 0;
  vector<i64> v;
  i64 sum = 0;
  for (i64 i = 1; i < vs.size(); i++) {
    if (imos[i - 1] == 0) sum += vs[i] - vs[i - 1];
    else v.push_back(vs[i] - vs[i - 1]);
  }
  i64 p = n - sum;
  ans += mint(sum) * mint(sum);
  ans += mint(sum) * mint(p) / 2;
  for (i64 x : v) {
    ans += mint(x) * mint(x) / 2;
    ans += mint(x) / 2 * (mint(p - x) / 2 + sum);
  }
  ans *= mint(2).pow(m);
  cout << ans.val() << "\n";
}
0