Submission #764566

#	Time	Username	Problem	Language	Result	Execution time	Memory
764566		1075508020060209tc	Grudanje (COCI19_grudanje)	C++14	70 / 70	1647 ms	20468 KiB

grudanje

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
int lowbit(int x){return x&-x;}
int bit[300005];
void upd(int pl,int x){
    while(pl<=100000){
        bit[pl]+=x;
        pl+=lowbit(pl);
    }
}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
int n;int Q;
string s;
int ans;
int ql[200005];int qr[200005];
int ar[200005];
int ansq[200005];
int nwchar;

void precalc(int l,int r){
for(int i=l;i<=r;i++){
    int c=s[ar[i]]-'a';
    if(c!=nwchar){continue;}
    upd(ar[i],-1);
}
}
void undo(int l,int r){
for(int i=l;i<=r;i++){
    int c=s[ar[i]]-'a';
    if(c!=nwchar){continue;}
    upd(ar[i],1);
}
}




void totalbs(int l,int r,vector<int>qryid){
if(l==r){
    for(int i=0;i<qryid.size();i++){
        ansq[qryid[i]]=l;
    }
    return;
}
int mi=(l+r)/2;
precalc(l,mi);
vector<int>lqid;vector<int>rqid;
for(int i=0;i<qryid.size();i++){
    int id=qryid[i];
    int cnt=qsum(qr[id])-qsum(ql[id]-1);
    if(cnt<=1){
        lqid.push_back(id);
    }else{
        rqid.push_back(id);
    }
}
totalbs(mi+1,r,rqid);
undo(l,mi);
totalbs(l,mi,lqid);
}


signed main(){
cin>>s;
n=s.size();
s="*"+s;
cin>>Q;
for(int i=1;i<=Q;i++){
    cin>>ql[i]>>qr[i];
}
for(int i=1;i<=n;i++){
    cin>>ar[i];
}
ans=0;
for(int i=0;i<=27;i++){
    nwchar=i;
    for(int j=0;j<=100000;j++){
        bit[j]=0;
    }
    vector<int>v;
    for(int j=1;j<=Q;j++){
        v.push_back(j);
    }

    for(int j=1;j<=n;j++){
        int c=s[j]-'a';
        if(c==nwchar){
            upd(j,1);
        }
    }

    totalbs(1,n,v);
    for(int j=1;j<=Q;j++){
        ans=max(ans,ansq[j]);
      //  cout<<ansq[j]<<" ";
    }
    //cout<<ans<<endl;
}
cout<<ans<<endl;

}

Compilation message (stderr)

grudanje.cpp: In function 'void totalbs(int, int, std::vector<int>)':
grudanje.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<qryid.size();i++){
      |                 ~^~~~~~~~~~~~~
grudanje.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 | for(int i=0;i<qryid.size();i++){
      |             ~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7