結果
問題 | No.1439 Let's Compare!!!! |
ユーザー |
![]() |
提出日時 | 2021-03-26 21:42:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 2,645 bytes |
コンパイル時間 | 2,200 ms |
コンパイル使用メモリ | 202,148 KB |
最終ジャッジ日時 | 2025-01-19 22:04:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } template <typename T> struct SegmentTree{ using F = function<T(T,T)>; int n; F f; T ti; vector<T> dat; SegmentTree(F f,T ti):f(f),ti(ti){} void init(int n_){ n=1; while(n<n_) n<<=1; dat.assign(n<<1,ti); } void build(const vector<T> &v){ int n_=v.size(); init(n_); for(int i=0;i<n_;i++) dat[n+i]=v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]); } void set_val(int k,T x){ dat[k+=n]=x; while(k>>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T query(int a,int b){ if(a>=b) return ti; T vl=ti,vr=ti; for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } template<typename C> int max_right(int s,C &check,T &acc,int k,int l,int r){ if(l+1==r){ acc=f(acc,dat[k]); return check(acc)?-1:k-n; } int m=(l+r)>>1; if(m<=s) return max_right(s,check,acc,(k<<1)|1,m,r); if(s<=l and check(f(acc,dat[k]))){ acc=f(acc,dat[k]); return -1; } int vl=max_right(s,check,acc,(k<<1)|0,l,m); if(~vl) return vl; return max_right(s,check,acc,(k<<1)|1,m,r); } // max t s.t. check(query(s,t)) // O(\log N) template<typename C> int max_right(int s,C &check){ assert(s<n and check(ti) and not check(query(s,n))); T acc=ti; return max_right(s,check,acc,1,0,n); } }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; string s,t; cin>>s>>t; auto calc=[&](char a,char b){ if(a==b) return 0; if(a<b) return -1; if(a>b) return +1; abort(); }; auto f=[&](int a,int b){return a?a:b;}; SegmentTree<int> seg(f,0); vector<int> vs(n); for(int i=0;i<n;i++) vs[i]=calc(s[i],t[i]); seg.build(vs); int q; cin>>q; for(int i=0;i<q;i++){ string c; int x,y; cin>>c>>x>>y; x--; if(c=="S") s[x]=y+'0'; if(c=="T") t[x]=y+'0'; seg.set_val(x,calc(s[x],t[x])); if(seg.query(0,n)==0){ cout<<"="<<newl; continue; } auto pred=[&](int a){return a==0;}; int k=seg.max_right(0,pred); cout<<(s[k]<t[k]?"<":">")<<newl; } return 0; }