結果

問題 No.3366 Reversible Tile:Revival
コンテスト
ユーザー akua
提出日時 2025-11-18 23:37:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,024 bytes
コンパイル時間 1,945 ms
コンパイル使用メモリ 143,384 KB
実行使用メモリ 24,972 KB
最終ジャッジ日時 2025-11-18 23:37:56
合計ジャッジ時間 15,057 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque #include <unordered_map> // unordered_map #include <unordered_set> // unordered_set #include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
#include <functional>
#include<unordered_map>
#include <random>
#include<bitset>
#include<cassert>
#include<chrono>
//#include <bits/stdc++.h>
using namespace std;  
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
//#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define arr(x) (x).rbegin(),(x).rend()
//typedef long long ll;
typedef unsigned long long ull;
typedef long long ll;
const ll inf=1e18;  
using vi=vector<int>;
using P= pair<ll,ll>;  
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vll=vector<ll>; 
using vvll=vector<vll>;
using vp=vector<P>;
using vvp=vector<vp>;
template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
int vx[]={0,1,0,-1,-1,1,1,-1},vy[]={1,0,-1,0,1,1,-1,-1};

//https://github.com/KentaroMatsushita/icpc_library/blob/main/src/modint/modint.hpp
constexpr int mod = 998244353;
struct mint {
   int x;
   mint(ll x_ = 0) : x(x_ % mod) {
      if(x < 0) x += mod;
   }
   mint operator-() {
      auto res = *this;
      res.x = (x ? mod - x : 0);
      return res;
   }
   mint& operator+=(mint r) {
      if((x += r.x) >= mod) x -= mod;
      return *this;
   }
   mint& operator-=(mint r) {
      if((x -= r.x) < 0) x += mod;
      return *this;
   }
   mint& operator*=(mint r) {
      x = 1LL * x * r.x % mod;
      return *this;
   }
   mint& operator/=(mint r) { return *this *= r.inv(); }
   friend mint operator+(mint a, mint b) { return a += b; }
   friend mint operator-(mint a, mint b) { return a -= b; }
   friend mint operator*(mint a, mint b) { return a *= b; }
   friend mint operator/(mint a, mint b) { return a /= b; }
   mint inv() const { return pow(mod - 2); }
   mint pow(ll b) const {
      mint a = *this, c = 1;
      while(b) {
         if(b & 1) c *= a;
         a *= a;
         b >>= 1;
      }
      return c;
   }
};
using vm = vector<mint>;

void solve(int test){
    ll L,m; cin >> L >> m;
    vll l(m),r(m);
    rep(i,m);
    rep(i,m)cin >> l[i] >> r[i];
    vll vs;
    vs.push_back(1);
    vs.push_back(L);
    rep(i,m){
        vs.push_back(l[i]);
        vs.push_back(r[i]);
        if(l[i]-1>=1)vs.push_back(l[i]-1);
        if(r[i]+1<=L)vs.push_back(r[i]+1);
    }
    sort(all(vs));
    vs.erase(unique(all(vs)),vs.end());
    int si=vs.size();
    vm val(si);
    vm ha(m);
    rep(i,m)ha[i]=rand()%mod;
    vm imos(si);
    rep(i,m){
        int nl=lower_bound(all(vs),l[i])-vs.begin();
        int nr=lower_bound(all(vs),r[i])-vs.begin();
        imos[nl]+=ha[i];
        if(nr+1<si)imos[nr+1]-=ha[i];
    }
    repi(i,1,si)imos[i]+=imos[i-1];
    ll zero=0;
    map<ll,ll> mp;
    rep(i,si){
        ll len=1;
        if(i!=si-1){
            len=vs[i+1]-vs[i];
        }
        if(imos[i].x==0)zero+=len;
        else {
            mp[imos[i].x]+=len;
        }
    }
//    cout << zero << endl;
    mint ans=0;
    ans+=mint(zero)*zero;
    ans+=mint(zero)*(L-zero)*2/2;
    ans+=mint(L-zero)*(L-zero)/4;
    for(auto u:mp){
        ans+=mint(u.second)*(u.second)/4;
    }
    rep(i,m)ans*=2;
    cout << ans.x << endl;
















}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int t=1;//cin >>t;
    rep(test,t)solve(test);
}
0