shekabhi1208's blog

By shekabhi1208, history, 3 years ago, In English

Link to Problem:-


can Someone please help me with my is not working for some test cases..i have tried many test cases but could'nt find out my mistake

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

3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you help me with this? Its showing TLE but time complexity is nlogn.


using namespace std; const long long M=1e9+7; const int N=5e4+10;

int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int t=1; // cin>>t; while(t--){ long long n; cin>>n; vector<pair<pair<int, int>, int>> v(n); for(int i=0; i<n; i++){ cin>>v[i].first.first>>v[i].first.second; v[i].second=i; } sort(v.begin(), v.end()); vector ans(n); set<pair<int, int>> a; a.insert({v[0].first.second, 0}); ans[v[0].second]=0; for(int i=1; i<n; i++){ int z=v[i].first.first; pair<int, int> p={z, -1}; auto it=lower_bound(a.begin(), a.end(), p); if(it==a.begin()){ a.insert({v[i].first.second, a.size()}); ans[v[i].second]=a.size()-1; } else{ it--; pair<int, int> p=*(it); ans[v[i].second]=p.second; a.erase(it); a.insert({v[i].first.second,p.second}); } } cout<<a.size()<<endl; for(int i=0; i<n; i++){ cout<<ans[i]+1<<" "; } cout<<endl; }