I think map is blowing up the time, you don’t actually need to use it
I have used almost the same approach where I have preprocessed the answers for all indexes in O(N) time and answered the queries in O(1) so the code works in the same complexity i.e O(Q+N) and also used fast io. Can someone please review and point out where I went wrong. I got TLE in this submission.
It is just due to server load being high during the contest! Sad, but true.
1 Like
I thing map takes unordered map in c++ uses O(1) time, then how would it give TLE…
Map doesn’t have O(1) time complexity, always. When you have large number of keys, it is O(log n), for nearly every function, be it, insertion, update, deletion or search.
Can anyone help me find what’s wrong (or can give TCs ) in my solution ?
https://www.codechef.com/viewsolution/35685158
Please Let me Know where I am going wrong,any tc ?
Good to know, I’ll add those snippets to my template right away 
1 Like
I got my error, I was just not clearing the unordered_map in every tc
Try this test case:
)())((()
8
1 2 3 4 5 6 7 8
correct answer is: 3 3 -1 -1 -1 -1 8 -1
while your code is giving:3 3 8 8 -1 -1 8 -1
1 Like
what’s the problem with my solution
#include
#include
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
string str;
cin>>str;
long long q;
cin>>q;
while(q–){
long long n;
cin>>n;
long long count=0;
bool printed=false;
for(long long i=n-1;i<str.length();i++){
if(str[i]==’(’){
count++;
printed=true;
}
if(str[i]==’)’ && count>0){
count–;
printed=true;
}
if(count==0 && printed==true){
cout<<i+1<<endl;
break;
}
if(i==str.length()-1 && count!=0){
cout<<"-1"<<endl;
}
}
}
}
// your code goes here
return 0;
}
exactly
The map you are using is the main reason
What does Non - empty balanced bracket subsequence mean? I know what is balanced, i also know what is a subsequence but what does non-empty signifies here?
i lost almost 15 minutes . they have to recheck the solution and then have updated the result that will be much better . hope no error like this next time .
AC. Thanks.
https://www.codechef.com/viewsolution/35718186
Can you please tell why, i am getting TLE?
Thanx in advanced