Ahmed_Allawati's blog

Strange TLE on problem F from last div 4

By Ahmed_Allawati, history, 7 weeks ago, In English

In the last div 4 round I submitted a solution to this problem 1791F - Range Update Point Query which failed at the main tests and get TLE on test 66
I almost use the same idea mentioned in the editoiral and i have no idea why this code gives TLE
here is the submission : 191992725
can anybody help please

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

»
7 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Ahmed_Allawati You have to clear the set s after each testcase.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In

for(int i=l;i<=r;i++) { auto it=s.lower_bound(i); if(it==s.end()) break; if(*it>r) break; replace(i); }

you are replacing a[i], but you need to replace a[*it]. Because of this your solve's asymptothics if O(q*n*log), not (q*log). I propose you to do it like this:

int i = l; while(i <= r){ auto it = s.lower_bound(i); if(it==s.end()) break; if(*it>r) break; i = *it; replace(i, s, a); ++i; }

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and you need to clear set too

    → Reply
    • »
      »
      »
      7 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      void replace(int i, set &s, vector &a) { int c=a[i]; int ans=0; while(c > 0) { ans += c % 10; c /= 10; } a[i] = ans ; if(a[i]<10) { if(s.find(i) != s.end()) s.erase(i); } }

      int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

      int t;
cin>>t;
while(t--){
        //set<int>::iterator it;
    set<int> s;
    int n,q;
    cin>>n>>q;
    vector <int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        s.insert(i);
    }
    while(q--){
        int T;
        cin>>T;
        if(T==1){
            int l,r;
            cin>>l>>r;
            l--; r--;
          //  cout<<l<<" "<<r<<endl;
            int i = l;
            while(i <= r){
                auto it = s.lower_bound(i);
                if(it==s.end()) 
                    break;
                if(*it>r) 
                    break;
                i = *it;
                replace(i, s, a);
                ++i;
            }
        }
        else {
            int x;
            cin>>x;
            x--;
            cout<<a[x]<<'\n';
        }
    }
}

      }

      this is your code after my debug, i swap string a to int a too, but i don't think, that it is important.

      you can check this code on my submission #192255747

      → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes i see .. thanks a lot
    what a stupid mistake i made

    → Reply