not_a_genius's blog

By not_a_genius, history, 22 months ago, In English
void solve(){
  I n,c,q;
  cin>>n>>c>>q;
  S s;
  cin>>s;
  vector<pair<int,int>> v;
  V(I) p(c+1);
  p[0]=n;
  for(I i=0;i<c;i++){
    I x,y;
    cin>>x>>y;
    v.pb({x,y});
    p[i+1]=p[i]+y-x+1;
  }
  while(q--){
    I k;
    cin>>k;
    while(k>n){
      I ind=lb(all(p),k)-p.begin()-1;
      I x=v[ind].ff;
      k-=p[ind];
      k=x+k-1;
    }
    cout<<s[k-1]<<endl;
  }
}

Provided above is my code for problem C of yesterday's contest. It gave a runtime error on test 2. Using a while loop I found out that the k value was becoming 0. However, according to my logic k value would never be zero. The array p denotes the length of the final string after every operation on it with the 0th index denoting the original length of the string. As I am performing a lower bound on k and then subtracting 1 from it therefore I am always assured that the value in array p would be less than k therefore, k-p[ind] would always be greater than or equal to 1. In addition, as x is 1 based index therefore x+k-1 would be a value greater than equal to 1. In addition, I can also prove that the value of ind would never be less than zero as I am applying a lower bound on a value greater than n and n is always present in my array. Can somebody please help me figure out if I am missing a point here?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it