#843764 (C++17) No.2230 Good Omen of White Lotus

• 問題: No.2230 Good Omen of White Lotus
• ユーザー: kmjp
• 提出日時: 2023-02-24 23:02:13
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 160 ms / 2,000 ms
• コード長: 1,937 bytes
• コンパイル時間: 1,716 ms
• コンパイル使用メモリ: 205,472 KB
• 最終ジャッジ日時: 2025-02-10 22:12:17
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 44

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------
int H,W,N,P;
vector<pair<int,int>> V;
template<class V,int NV> class SegTree_1 {
public:
    vector<V> val;
    static V const def=0;
    V comp(V l,V r){ return max(l,r);};
    
    SegTree_1(){val=vector<V>(NV*2,def);};
    V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
        if(r<=x || y<=l) return def;
        if(x<=l && r<=y) return val[k];
        return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
    }
    void update(int entry, V v) {
        entry += NV;
        val[entry]=comp(v,val[entry]); //上書きかチェック
        while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
    }
};
SegTree_1<int,1<<20> st;
const ll mo=998244353;
ll modpow(ll a, ll n = mo-2) {
    ll r=1;a%=mo;
    while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
    return r;
}
void solve() {
    int i,j,k,l,r,x,y; string s;
    
    cin>>H>>W>>N>>P;
    FOR(i,N) {
        cin>>x>>y;
        V.push_back({x,y});
    }
    sort(ALL(V));
    int ma=0;
    FORR2(x,y,V) {
        k=st.getval(0,y+1)+1;
        ma=max(ma,k);
        st.update(y,k);
    }
    
    int ng=H+W-3-ma;
    //全部アウト
    ll ret=1;
    FOR(i,ma) ret=ret*(mo+1-2*modpow(P)%mo)%mo;
    FOR(i,ng) ret=ret*(mo+1-modpow(P)%mo)%mo;
    
    cout<<(mo+1-ret)%mo<<endl;
    
}
int main(int argc,char** argv){
    string s;int i;
    if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
    FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
    cout.tie(0); solve(); return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX