提出 #38071693

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;const int N=100010;set<int>e[26];int n,q,op,x,y,c[N];char ch,str[N];bool fl,p[N];void add(int x,int v){if(p[x])for(;x<n;x+=x&-x)c[x]+=v;}int sum(int x){int res=0;for(;x;x^=x&-x)res+=c[x];return res;}bool sum(int x,int y){return sum(y)!=sum(x-1);}bool F(int x,int l,int r){return e[x].size()&&*--e[x].end()>=l&&*e[x].lower_bound(l)<=r;}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>n>>(str+1)>>q;for(int i=1;i<=n;++i)e[str[i]-'a'].insert(i);for(int i=1;i<n;++i)p[i]=str[i]>str[i+1],add(i,1);for(;q--;){cin>>op>>x;if(op==1){cin>>ch;if(x>1)add(x-1,-1);if(x<n)add(x,-1);e[str[x]-'a'].erase(x),str[x]=ch,e[ch-'a'].insert(x);if(x>1)p[x-1]=str[x-1]>str[x],add(x-1,1);if(x<n)p[x]=str[x]>str[x+1],add(x,1);}else{cin>>y;if(sum(x,y-1))fl=0;else{fl=1;for(int i=str[x]-'a'+1;i<str[y]-'a';++i)if((x>1&&F(i,1,x-1))||(y<n&&F(i,y+1,n))){fl=0;break;}}cout<<(fl?"Yes\n":"No\n");}}return 0;}

提出情報

提出日時
問題 F - Substring of Sorted String
ユーザ Treap
言語 C++ (GCC 9.2.1)
得点 500
コード長 933 Byte
結果 AC
実行時間 103 ms
メモリ 8872 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 1
AC × 24
セット名 テストケース
Sample sample_01.txt
All hand.txt, min.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, sample_01.txt
ケース名 結果 実行時間 メモリ
hand.txt AC 6 ms 3652 KiB
min.txt AC 4 ms 3604 KiB
random_01.txt AC 62 ms 8456 KiB
random_02.txt AC 64 ms 8424 KiB
random_03.txt AC 57 ms 8432 KiB
random_04.txt AC 68 ms 8428 KiB
random_05.txt AC 55 ms 8432 KiB
random_06.txt AC 56 ms 8368 KiB
random_07.txt AC 51 ms 8356 KiB
random_08.txt AC 61 ms 8416 KiB
random_09.txt AC 58 ms 8484 KiB
random_10.txt AC 59 ms 8452 KiB
random_11.txt AC 47 ms 8380 KiB
random_12.txt AC 52 ms 8452 KiB
random_13.txt AC 56 ms 8872 KiB
random_14.txt AC 60 ms 8736 KiB
random_15.txt AC 77 ms 8812 KiB
random_16.txt AC 66 ms 8452 KiB
random_17.txt AC 94 ms 8376 KiB
random_18.txt AC 69 ms 8456 KiB
random_19.txt AC 103 ms 8480 KiB
random_20.txt AC 66 ms 8452 KiB
random_21.txt AC 101 ms 8460 KiB
sample_01.txt AC 3 ms 3468 KiB