結果
問題 | No.2080 Simple Nim Query |
ユーザー | momoyuu |
提出日時 | 2023-05-20 02:09:44 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 687 ms / 3,000 ms |
コード長 | 2,619 bytes |
コンパイル時間 | 3,353 ms |
コンパイル使用メモリ | 251,448 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 07:47:16 |
合計ジャッジ時間 | 7,890 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 202 ms
6,944 KB |
testcase_04 | AC | 206 ms
6,940 KB |
testcase_05 | AC | 675 ms
6,944 KB |
testcase_06 | AC | 657 ms
6,940 KB |
testcase_07 | AC | 657 ms
6,940 KB |
testcase_08 | AC | 662 ms
6,944 KB |
testcase_09 | AC | 687 ms
6,944 KB |
testcase_10 | AC | 85 ms
6,944 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; template< typename T > struct segtree{ using F = function<T(T,T)>; int n; F f; T e; vector<T> data; /* * n:鬆らせ謨ー * f:貍皮ョ・ * e:蜊倅ス榊・ */ segtree(int n,F f,T e):f(f),e(e){ this->n = 1; while(this->n<n) (this->n)<<=1; data.assign(2*(this->n),e); } void set(vector<T> &a){ for(int i = 0;i<n;i++){ data[i+n-1] = a[i]; } } void set(int i,T x){ data[i+n-1] = x; } void build(){ for(int i = n - 2;i>=0;i--){ data[i] = f(data[2*i+1],data[2*i+2]); } } void update(int i,T x){ int ni = i + n - 1; data[ni] = x; while(ni>0){ ni = (ni-1)/2; data[ni] = f(data[2*ni+1],data[2*ni+2]); } } T query(int a,int b){ T ans = e; a += n-1; b--;b += n-1; while(a>=0&&b>=0&&a<=b){ if(a==b){ ans = f(ans,data[a]); break; } if(!(a&1))ans = f(ans,data[a]); if(b&1)ans = f(ans,data[b]); a++;b--; a = (a-1)/2;b = (b-1)/2; } return ans; } T operator[](const int i) const { return data[i+n-1]; } }; int cmp(int a,int b){return a+b;} int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,q; cin>>n>>q; segtree<int> seg(n,cmp,0); vector<int> a(n); for(int i = 0;i<n;i++) cin>>a[i]; for(int i = 0;i<n;i++) seg.update(i,(a[i]>=2?1:0)); while(q--){ int op; cin>>op; if(op==1){ int x,y; cin>>x>>y; x--; a[x] = y; seg.update(x,(a[x]>=2?1:0)); }else{ int l,r; cin>>l>>r; l--;r--; int now = 1; now = seg.query(l+1,r+1); if(now==0){ if((r-l+1)%2){ cout<<"F\n"; }else{ cout<<"S\n"; } continue; } int left = l + 1; int right = r + 1; while(right-left>1){ int mid = (right+left)/2; if(seg.query(l+1,mid)>=now) right = mid; else left = mid; } //cout<<r<<" "<<right<<endl; if((r-right+1)%2==0){ cout<<"F"<<endl; }else{ cout<<"S"<<endl; } } } }