結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
|
提出日時 | 2023-05-19 21:37:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 1,519 bytes |
コンパイル時間 | 918 ms |
コンパイル使用メモリ | 81,328 KB |
実行使用メモリ | 35,548 KB |
最終ジャッジ日時 | 2024-12-18 02:23:35 |
合計ジャッジ時間 | 10,305 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#include<iostream> #include<vector> #include<cassert> #include<atcoder/segtree> using namespace std; //1-indexed #include<vector> template<typename T> struct BIT{ int n; vector<T>bit; BIT(int n_=0):n(n_),bit(n_+1){} T sum(int i) { T ans=0; for(;i>0;i-=i&-i)ans+=bit[i]; return ans; } void add(int i,T a) { if(i==0)return; for(;i<=n;i+=i&-i)bit[i]+=a; } int lower_bound(T k)//k<=sum(ret) { if(k<=0)return 0; int ret=0,i=1; while((i<<1)<=n)i<<=1; for(;i;i>>=1) if(ret+i<=n&&bit[ret+i]<k)k-=bit[ret+=i]; return ret+1; } }; pair<int,int>op(pair<int,int>l,pair<int,int>r){return max(l,r);} pair<int,int>e(){return make_pair(-1,-1);} int N; string X[2<<17]; string Y[2<<17]; atcoder::segtree<pair<int,int>,op,e>seg; bool f(int l,int r) { if(l==r)return X[l]=="True"; int idx=seg.prod(l,r).second; bool L=f(l,idx),R=f(idx+1,r); //cout<<l<<" "<<r<<" sp at "<<idx<<" : "<<L<<" "<<R<<endl; if(Y[idx]=="and")return L&&R; else if(Y[idx]=="or")return L||R; else if(Y[idx]=="xor")return L!=R; else return !L||R; } int main() { int T;cin>>T; for(;T--;) { cin>>N; for(int i=0;i<N;i++)cin>>X[i]; for(int i=0;i<N-1;i++)cin>>Y[i]; BIT<int>bit(N-1); for(int i=1;i<=N-1;i++)bit.add(i,1); vector<pair<int,int> >init(N-1,e()); for(int i=0;i<N-1;i++) { int s;cin>>s; int idx=bit.lower_bound(s)-1; assert(init[idx]==e()); init[idx]=make_pair(i,idx); bit.add(idx+1,-1); } seg=atcoder::segtree<pair<int,int>,op,e>(init); cout<<(f(0,N-1)?"True\n":"False\n"); } }