https://codeforces.com/problemset/problem/1491/A

i am using a set to store here instead of a vector but its giving me tle but my program should execute well under time limit
please tell me where its taking that much time
/*

ANIKET ASH

*/

#include<bits/stdc++.h>

using namespace std;

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define ll long long int

#define pb push_back

#define pf push_front

#define pi 3.14159265358979323846

#define mod 1000000007

#define mp make_pair

#define ff first

#define ss second

#define nline ‘\n’

#ifndef ONLINE_JUDGE

#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;

#else

#define debug(x)

#endif

void _print(int t) {cerr << t;}

void _print(string t) {cerr << t;}

void _print(char t) {cerr << t;}

void _print(double t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);

template void _print(vector v);

template void _print(set v);

template <class T, class V> void _print(map <T, V> v);

template void _print(multiset v);

template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.ff); cerr << “,”; _print(p.ss); cerr << “}”;}

template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}

template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}

template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}

template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}

void solve()

{

int n,q;

cin>>n>>q;

vector a;

multiset b;

for(int i=0;i<n;i++)

{

int x;

cin>>x;

a.pb(x);

b.insert(x);

}

while(q–)

{

int r,t;

cin>>t>>r;

if(t==1)

{ auto it=b.find(a[r-1]);

b.erase(it);



  a[r-1]=1-a[r-1];

 

  b.insert(a[r-1]);

}

if(t==2)

{

auto it=b.end();

it--;

int k=1;

for(it;;it--)

{

    if(k==r){

    cout<<*it<<nline;

   break;

    }

    k++;

}

}

}

}

int main()

{

#ifndef ONLINE_JUDGE

freopen(“input.txt”, “r”, stdin);

freopen("output.txt", "w", stdout);

freopen(“error.txt”, “w”, stderr);

#endif

ios

int t=1;

// cin>>t;

while(t–)

{

solve();

}

return 0;

}

As for this question we only have 1’s and 0’s in an array so you can simply count frequency of 1’s and 0’s and when ever you have to answer a query you can use the fact that number whose frequency is greater in then k is your answer.

As for updates you have all values stored in vector so whenever index get flipped you will simply have to change frequency of 1’s and 0’s by amount on 1.

This way you are dealing with every query in O( 1 ) time.

here is my code for better understanding of what i have told

void solve()
{
    /// IF THERE IS SINGLE TEST CASE MAKE t = 1 in main()
 
    int n , q ;
    cin >> n >> q ;
 
    vector< int > a( n ) ;
 
    int zero = 0 , one = 0 ;
 
    for( int i = 0 ; i < n ; i++ )
    {
        cin >> a[ i ] ;
        if( a[ i ] == 0 )
            zero++ ;
        else
            one++ ;
    }
 
    while( q-- )
    {
        int x , k ;
        cin >> x >> k ;
 
        if( x == 1 )
        {
            --k ;
            if( a[ k ] == 0 )
                a[ k ] += 1 , zero-- , one++ ;
            else
                a[ k ] -= 1 , zero++ , one-- ;
        }
        else
        {
            if( one >= k )
                cout << "1\n" ;
            else
                cout << "0\n" ;
        }
    }
}
 
int main()
{
    int t ;
    t = 1 ;
 
    while( t-- )
        solve() ;
 
    return 0 ;
}

yes bro i already solved with that but my code is also o(n*log(n) i.e logn time for inserting in map right ??? so its well under 1 sec btw thanks for answering☺