TLE in FLIPCOIN

general
1 
using namespace std;
int main()
{
  long long  int N;
    long long int q;
    int start;
    int end1;
    int ch;
    int cnt=0;
    cin>>N;
   int coins[N]={0};
   cin>>q;
   while(q--)
   {
       cin>>ch>>start>>end1;
       if(ch==0)
       {
           for(int i=start;i<=end1;i++)
           {
               coins[i]=1;
           }
       }
       else if(ch==1)
       {
             for(int i=start;i<=end1;i++)
           {
              if(coins[i]==1)
              {
                  cnt++;
              }
           }
           cout<<cnt<<endl;
       }
       else
       break;
   }
return 0;
}

im getting TLE pls help what shouldi do ?how to handle time complexity?

2

Format your code. Use ``` symbol at the start and end of code

3

ok

4

pls see my doubt @sebastian

5

This can be done in O(1).

while(g--)
    {
        int n,i,q;
        cin>>i>>n>>q;
        if(n%2==0)
        cout<<n/2<<"\n";
        else
        {
            if(q!=i)
            cout<<n/2+1<<"\n";
            else
            cout<<n/2<<"\n";
        }
    }
1 Like
6

i did not get what u did?

8

@otutsukihyuuga pls see this?

9

@sebastian are you really talking about FLIPCOIN Problem - CodeChef

1 Like
10

Oh sorry, I thought CodeChef: Practical coding for everyone

1 Like
11

Both your update and query operations work in O(n). Since there are q queries, therefore the time complexity of your code is O(nq), which is 10^5 * 10^5 = 10^{10} operations, which TLEs. This problem can be solved using Segment Trees with lazy propagation. Segment Trees can perform both update and query operations in O(\log n). You can read about Segment Trees here.

1 Like
12

Just use a lazy segment tree.

1 Like
13

ok thanks @anon49701446 and @everule1 will see the article

1 Like