Header Ad

HackerEarth String query problem solution

In this HackerEarth String query problem solution we have given a string s and m queries. For each query delete the K-th occurrence of a character x.


HackerEarth String query problem solution


HackerEarth String query problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 5000000007
#define total 500005
#define M 1000000007
#define NIL 0
#define INF (1<<28)
#define MAXN 200001
typedef unsigned long long int uint64;
typedef long long int int64;


int BIT[27][MAXN];
void update(int loc,int x,int vl){
for(int i=x;i<=MAXN;i+=(i&-i))
BIT[loc][i]+=vl;
}
int query(int loc,int x){
int ans=0;
for(int i=x;i>=1;i-=(i&-i))
ans+=BIT[loc][i];
return ans;
}
int remocu(int loc,int x){
int mid,lb=1,ub=MAXN,ans;
while(lb<=ub){
mid=((lb+ub)>>1);
if(query(loc,mid)>=x){
ans=mid;
ub=mid-1;
}
else
lb=mid+1;
}
update(loc,ans,-1);
return ans;
}
bool vis[2000004];
string p,s;
int main(){
int k,i,x,n;
char c;
cin>>s;
scanf("%d",&n);
for(i=0;i<s.size();i++){
update(s[i]-'a',i+1,1);
}
while(n--){
cin>>x>>c;
//cout<<x<<" "<<c;
c-='a';
int le=remocu(c,x);
//cout<<le<<endl;
vis[le-1]=1;
}
for(i=0;i<s.size();i++){
if(vis[i]==0)
printf("%c",s[i]);
}
printf("\n");
return 0;
}

Second solution

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ft first
#define sd second
#define VI vector<int>
#define VLL vector<long long int>
#define PII pair<int,int>
#define pb push_back
#define rsz(v,n) v.resize(n)
// input and output
#define scan(x) scanf("%d",&x)
#define scanll(x) scanf("%lld",&x)
#define ll long long int
#define rep(i,x,y) for(i=x;i<y;i++)
#define print(x) printf("%d\n",x)
#define printll(x) printf("%lld\n",x)
#define all(v) v.begin(),v.end()
#define ms(v) memset(v,0,sizeof(v))
#define FOR(i,a,b) for(i=a;i<b;i++)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#ifdef ONLINE_JUDGE
inline void inp( int &n )
{
n=0;
int ch=getchar_unlocked();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
n=n*sign;
}
#else
inline void inp(int &n){
cin>>n;
}
#endif
string str;
struct node{
int F[26];

};
vector<node> st;

inline void buildst(int idx,int ss,int se){

if(ss==se){
for(int i=0;i<26;i++) st[idx].F[i]=0;
st[idx].F[str[ss]-'a']=1;
return ;
}
int mid=(ss+se)>>1;
buildst(2*idx+1,ss,mid);
buildst(2*idx+2,mid+1,se);
for(int i=0;i<26;i++) st[idx].F[i]=st[idx*2+1].F[i]+st[idx*2+2].F[i];
}

void update(int idx,int ss,int se,int val,int count){

if(ss==se){
st[idx].F[count]=0;
str[ss]='X';
return;
}
int mid=(ss+se)>>1;
if(st[2*idx+1].F[count]>=val){
update(2*idx+1,ss,mid,val,count);
}else{
update(2*idx+2,mid+1,se,val-st[2*idx+1].F[count],count);
}
for(int i=0;i<26;i++) st[idx].F[i]=st[idx*2+1].F[i]+st[idx*2+2].F[i];
}
int main()
{
// std::ios_base::sync_with_stdio(false);
int t;
t=1;
while(t--){
cin>>str;
int n=str.length();
int size=(ceil)(log2(n))+1;
st.resize(1<<size);
buildst(0,0,n-1);
int q;
inp(q);
int val,count;
char ch;
while(q--){
inp(val);
cin>>ch;
count=ch-'a';
update(0,0,n-1,val,count);
}

for(int i=0;i<n;i++){
if(str[i]!='X')
cout<<str[i];
}
cout<<endl;
}
return 0;
}


Post a Comment

0 Comments