I used rope. (For more information Implicit cartesian tree in GNU C++ STL. - Codeforces)
// #includes ...
#include <ext/rope>
using namespace __gnu_cxx;
using namespace std;
crope S;
char x[MAX_N];
// inserting x into i
void insert(int i){
S.insert(S.mutable_begin() + i, x);
}
void query(int i, int len){
for(int j = 0; j < len; j++){
putchar(S[i + j - 1]);
}
putchar('\n');
}
10 Likes
Using the built-in functions for string, str.insert for inserting and str.substr for printing the substring gave me 100 points!
Here is the AC solution.
Weak Test Cases…?? If not then i am more interested in knowing their built-in implementations!!
7 Likes
This problem is the same as problem B from ACPC regional contest 2012
Link for the problem
2 Likes
Can anyone tell me why brute force solutions are getting accepted?
1 Like
I think this problem can also be solved with Treap(Balanced BST).
I am getting SIGSEGV for all test cases…I am using linked list can anyone help me?
http://www.codechef.com/viewsolution/4406111
I am getting SIGABRT for all test cases, here is my solution :
CodeChef: Practical coding for everyone can anyone help me?
I Didn’t Understand The Editorial , Can Someone Please Explain it to me ??
Problem is while printing the substring .
The second parameter is length not index … I did the same mistake …
1 Like
Mistake is in second type of query …
cin>>i>>l;
for(i--;i<l;i++)
cout<<b[i];
cout<<"\n";
Instead it should be
cin>>i>>l;
for( int f = i ; f < i + l; f++)
cout<<b[f];
cout<<"\n";
1 Like
Oh No :(…
Ruined the contest!!
Thanks Now.
that’s something new, but in the codeforces blog it uses rope , but you used crope. what’s the difference?
can someone tell me why my solution gives wa my submission id is CodeChef: Practical coding for everyone
I read the manual and found out that crope is just a wrapper for rope or similar.
Learned something new. Appreciate the fact that you called out your unique implementation in the comments, would have remained unware of Rope other wise
Thanks
Lone Coder
I think you are lucky …
My solution with same approach is not getting 100 and even I used same approach during contest, I got 50 only.
My Solution CodeChef: Practical coding for everyone
@gdisastery1 What i found is “rope” is taking more time(approx double) than simple std::string insert/substr based implementation. why??
String based @ CodeChef: Practical coding for everyone ,
rope based @ CodeChef: Practical coding for everyone
Use this to generate a test case: X1kXHB - Online Python Interpreter & Debugging Tool - Ideone.com with Python 2.7
On my computer, the std::string version is taking about ~2.5 seconds and the rope version only ~0.3 seconds.
1 Like