In this HackerEarth Gifts problem solution This festive Season HackerEarth decided to send gifts to all of its contributors. Xsquare , Sentinel , Subway , darkshadows and Venomous got their favourite gifts i.e ,an array full of integers. Contrary to that ma5termind got his favourite string str consisting of upper case letters ‘A’ , ‘B’ , ‘C’ , ‘D’ and ‘E’ only. To avoid any kind of comparison ,all the gifts are of same size i.e N. As HackerEarth promotes a very friendly culture, all of them have decided to play together with these gifts. For the purpose to serve …
- Xsquare named his array as A.
- Sentinel named his array as B.
- Subway named his array as C.
- Darkshadows named his array as D.
- Venomous named his array as E.
- They will mainly perform three types of task.
HackerEarth Gifts problem solution.
#include<bits/stdc++.h>
using namespace std;
#define MAX 100002
#define ll long long
#define ft first
#define sd second
ll A[5][MAX];
ll bit[120][MAX];
map<string , int > M;
int indexx;
void perm(string str,int idx,int n){
if(idx == n){
M[str] = indexx;
indexx++;
//cout << str << endl;
return ;
}
for(int i=idx;i<n;i++){
int cnt = i-idx;
int indx = i;
while(cnt--){
swap(str[indx],str[indx-1]);
indx--;
}
perm(str,idx+1,n);
cnt = i - idx;
indx = idx;
while(cnt--){
swap(str[indx],str[indx+1]);
indx++;
}
}
}
/*---------bit update ------------------*/
void update(int idx,ll val,int n,int b){
while(idx<=n){
bit[b][idx]+=val;
idx+=(idx&(-idx));
}
}
ll sum(int idx,int b){
ll s =0;
while(idx){
s+=bit[b][idx];
idx-=(idx&(-idx));
}
return s;
}
ll query(int l,int r,int b){
return sum(r,b)-sum(l-1,b);
}
int main(){
int n;
scanf("%d",&n);
assert(n>=1&&n<MAX);
string str;
for(int i=0;i<5;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&A[i][j]);
assert(A[i][j] <= 1000000000 && A[i][j] >= 1);
}
}
cin >> str;
assert(str.length() == n);
for(int i=0;i<n;i++)
str[i] = tolower(str[i]);
perm("abcde",0,5);
for(map<string,int> :: iterator it= M.begin() ; it!=M.end() ; it++){
for(int j=0;j<n;j++){
int indexx = (it->ft)[str[j]-'a']-'a';
update(j+1,A[indexx][j+1],n,it->sd);
}
}
int q;
scanf("%d",&q);
int queryidx = 0;
string s="abcde";
while(q--){
string type;
int l,r;
cin >> type;
if(type[1]=='c'){ // change
char ch;
cin >> l >> ch;
ch = tolower(ch);
str[l-1] = ch; // string update
l--;
for(map<string,int> :: iterator it= M.begin() ; it!=M.end() ; it++){
int indexx = (it->ft)[str[l]-'a']-'a';
update(l+1,A[indexx][l+1]-query(l+1,l+1,it->sd),n,it->sd);
}
}else if(type[1]=='e'){
char a,b;
cin >> a >> b;
a = tolower(a);
b = tolower(b);
swap(s[a-'a'],s[b-'a']);
queryidx = M[s]; // new index
}else{
scanf("%d",&l);
scanf("%d",&r);
assert(l<=r);
printf("%lldn",query(l,r,queryidx));
}
}
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
long long A[5][100005];
long long tree[121][100005];
string s;
int n;
map <string, int> m;
map <string, int> :: iterator it;
int cnt;
void update(int tree_idx, int idx, long long val)
{
while ( idx <= n+1 ) {
tree[tree_idx][idx] += val;
idx += (idx & (-idx));
}
return;
}
long long query(int tree_idx, int idx)
{
long long ans = 0;
while ( idx > 0 ) {
ans += tree[tree_idx][idx];
idx -= (idx & (-idx));
}
return ans;
}
void pre()
{
string p = "ABCDE";
cnt = 1;
do {
m[p] = cnt++;
}
while ( next_permutation(p.begin(),p.end()) );
return;
}
int main()
{
pre();
int q;
string str,init="ABCDE";
cin >> n;
for ( int i = 0; i < 5; i++ ) {
for ( int j = 1; j <= n; j++ ) cin >> A[i][j];
}
cin >> s;
s = "X" + s;
for ( it = m.begin(); it != m.end(); it++ ) {
int tree_idx = (*it).second;
string now = (*it).first;
for ( int i = 1; i <= n; i++ ) update(tree_idx, i, A[now[s[i]-65]-65][i]);
}
cin >> q;
while ( q-- ) {
cin >> str;
if ( str == "Qs" ) {
int a,b;
cin >> a >> b;
cout << query(m[init],b) - query(m[init],a-1) << endl;
}
else if ( str == "Qe") {
char a,b;
cin >> a >> b;
swap(init[a-65],init[b-65]);
}
else {
int a;
char b;
cin >> a >> b;
for ( it = m.begin(); it != m.end(); it++ ) {
int tree_idx = (*it).second;
string now = (*it).first;
long long val = query(tree_idx, a) - query(tree_idx, a-1);
update(tree_idx, a, A[now[b-65]-65][a]-val);
}
}
}
return 0;
}