This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<
const lo inf = 1000000000;
const lo li = 500005;
const lo mod = 1000000007;
int n,m,a[li],k,flag,t;
int cev;
string s,ss;
vector<int> v;
inline int fark(int x,int y){
if(x>y)return 26-x+y;
return y-x;
}
inline char ekle(int x,int y){
x+=y;
if(x>'z')x-=26;
return x;
}
struct segtree{
array<int,li*4> tree;
int md=0;
segtree(int x){
md=x;
}
inline void update(int node,int start,int end,int l,int r,int val){
if(start>end || start>r || end<l)return ;
if(start>=l && end<=r){if(md!=start%2)return ;tree[node]+=val;return ;}
update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
tree[node]=tree[node*2]+tree[node*2+1];
}
inline int query(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l)return 0;
if(start>=l && end<=r)return tree[node];
return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}
};
int32_t main(void){
fio();
cin>>n>>k;
cin>>s>>ss;
s="%"+s;
ss="%"+ss;
char myc=s[n];
for(int i=1;i<=n-1;i++){
int at=fark(s[i],ss[i]);
a[i]=at;
s[i]=ekle(s[i],at);
s[i+1]=ekle(s[i+1],at);
}
if(s[n]==ss[n]){cout<<"da\n";}
else cout<<"ne\n";
segtree st1(1);
segtree st2(0);
while(k--){
int i;char c;
cin>>i>>c;
if(i==n)myc=c;
int val=a[i-1]+st1.query(1,1,n,1,i-2)*(i%2?-1:1)+st2.query(1,1,n,1,i-2)*(i%2?1:-1)+26*100000000000;
int val2=a[i]+st1.query(1,1,n,1,i-1)*(i%2?1:-1)+st2.query(1,1,n,1,i-1)*(i%2?-1:1)+26*100000000000;
val%=26;val2%=26;
c=ekle(c,val);
int tut=fark(c,ss[i]);
st1.update(1,1,n,i,i,tut-val2);
st2.update(1,1,n,i,i,tut-val2);
val=a[n-1]+st1.query(1,1,n,1,n-2)*(n%2?-1:1)+st2.query(1,1,n,1,n-2)*(n%2?1:-1)+26*100000000000;
val%=26;
//cout<<val _ a[n-1] _ fark(s[n],ss[n])<<" () "<<endl;
if(val==fark(myc,ss[n]))cout<<"da\n";
else cout<<"ne\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |