GitHub - Dipankar-Kumar-Singh/Codeforces: My solutions to the problems of codeforces

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 3 Commits
HackerCup2023		HackerCup2023
AC_QUeen_Other.cpp		AC_QUeen_Other.cpp
A_-_Apple.cpp		A_-_Apple.cpp
A_1_Consecutive_Cuts_-_Chapter_1.cpp		A_1_Consecutive_Cuts_-_Chapter_1.cpp
A_2023.cpp		A_2023.cpp
A_2_-_3_Moves.cpp		A_2_-_3_Moves.cpp
A_ABC.cpp		A_ABC.cpp
A_A_B.cpp		A_A_B.cpp
A_A_Variety_of_Operations.cpp		A_A_Variety_of_Operations.cpp
A_Absolute_Maximization.cpp		A_Absolute_Maximization.cpp
A_Add_Plus_Minus_Sign.cpp		A_Add_Plus_Minus_Sign.cpp
A_Ancient_Civilization.cpp		A_Ancient_Civilization.cpp
A_Another_String_Minimization_Problem.cpp		A_Another_String_Minimization_Problem.cpp
A_Anti_Light_s_Cell_Guessing.cpp		A_Anti_Light_s_Cell_Guessing.cpp
A_Array_Balancing.cpp		A_Array_Balancing.cpp
A_Balanced_Substring.cpp		A_Balanced_Substring.cpp
A_Beat_The_Odds.cpp		A_Beat_The_Odds.cpp
A_Bestie.cpp		A_Bestie.cpp
A_Bits.cpp		A_Bits.cpp
A_Boredom.cpp		A_Boredom.cpp
A_Boy_or_Girl.cpp		A_Boy_or_Girl.cpp
A_Boys_and_Girls.cpp		A_Boys_and_Girls.cpp
A_Burenka_Plays_with_Fractions.cpp		A_Burenka_Plays_with_Fractions.cpp
A_CQXYM_Count_Permutations.cpp		A_CQXYM_Count_Permutations.cpp
A_Casimir_s_String_Solitaire.cpp		A_Casimir_s_String_Solitaire.cpp
A_Chat_room.cpp		A_Chat_room.cpp
A_Chip_Game.cpp		A_Chip_Game.cpp
A_Cinema_Line.cpp		A_Cinema_Line.cpp
A_Cirno_s_Perfect_Bitmasks_Classroom.cpp		A_Cirno_s_Perfect_Bitmasks_Classroom.cpp
A_Closing_The_Gap.cpp		A_Closing_The_Gap.cpp
A_Codeforces_Checking.cpp		A_Codeforces_Checking.cpp
A_Color_the_Picture.cpp		A_Color_the_Picture.cpp
A_Colored_Balls_Revisited.cpp		A_Colored_Balls_Revisited.cpp
A_Compare_T-Shirt_Sizes.cpp		A_Compare_T-Shirt_Sizes.cpp
A_Consecutive_Sum.cpp		A_Consecutive_Sum.cpp
A_Construct_a_Rectangle.cpp		A_Construct_a_Rectangle.cpp
A_Constructive_Problems.cpp		A_Constructive_Problems.cpp
A_Contest.cpp		A_Contest.cpp
A_Countdown.cpp		A_Countdown.cpp
A_Counting_Kangaroos_is_Fun.cpp		A_Counting_Kangaroos_is_Fun.cpp
A_Cowardly_Rooks.cpp		A_Cowardly_Rooks.cpp
A_Crossmarket.cpp		A_Crossmarket.cpp
A_Cut_Ribbon.cpp		A_Cut_Ribbon.cpp
A_Cut_the_Triangle.cpp		A_Cut_the_Triangle.cpp
A_DZY_Loves_Sequences.cpp		A_DZY_Loves_Sequences.cpp
A_D_j_Vu.cpp		A_D_j_Vu.cpp
A_Deletions_of_Two_Adjacent_Letters.cpp		A_Deletions_of_Two_Adjacent_Letters.cpp
A_Desorting.cpp		A_Desorting.cpp
A_Digit_Minimization.cpp		A_Digit_Minimization.cpp
A_Dislike_of_Threes.cpp		A_Dislike_of_Threes.cpp
A_Distinct_Buttons.cpp		A_Distinct_Buttons.cpp
A_Divan_and_a_Store.cpp		A_Divan_and_a_Store.cpp
A_Divide_and_Conquer.cpp		A_Divide_and_Conquer.cpp
A_Divide_and_Multiply.cpp		A_Divide_and_Multiply.cpp
A_Division.cpp		A_Division.cpp
A_Domino.cpp		A_Domino.cpp
A_Domino_Disaster.cpp		A_Domino_Disaster.cpp
A_Doors_and_Keys.cpp		A_Doors_and_Keys.cpp
A_Doremy_s_IQ.cpp		A_Doremy_s_IQ.cpp
A_Doremy_s_Paint.cpp		A_Doremy_s_Paint.cpp
A_Download_More_RAM.cpp		A_Download_More_RAM.cpp
A_Dragons.cpp		A_Dragons.cpp
A_Eevee.cpp		A_Eevee.cpp
A_Elections.cpp		A_Elections.cpp
A_Equal_or_Not_Equal.cpp		A_Equal_or_Not_Equal.cpp
A_Equidistant_Letters.cpp		A_Equidistant_Letters.cpp
A_Escape_from_Stones.cpp		A_Escape_from_Stones.cpp
A_Everyone_Loves_to_Sleep.cpp		A_Everyone_Loves_to_Sleep.cpp
A_Everything_Everywhere_All_But_One.cpp		A_Everything_Everywhere_All_But_One.cpp
A_Exponential_Equation.cpp		A_Exponential_Equation.cpp
A_Extremely_Round.cpp		A_Extremely_Round.cpp
A_Ezzat_and_Two_Subsequences.cpp		A_Ezzat_and_Two_Subsequences.cpp
A_Factorise_N_M.cpp		A_Factorise_N_M.cpp
A_Factory.cpp		A_Factory.cpp
A_Fancy_Fence.cpp		A_Fancy_Fence.cpp
A_Filling_Shapes.cpp		A_Filling_Shapes.cpp
A_Find_Array.cpp		A_Find_Array.cpp
A_Flip_Flop_Sum.cpp		A_Flip_Flop_Sum.cpp
A_Flipping_Game.cpp		A_Flipping_Game.cpp
A_Food_for_Animals.cpp		A_Food_for_Animals.cpp
A_Football.cpp		A_Football.cpp
A_Forbidden_Subsequence.cpp		A_Forbidden_Subsequence.cpp
A_Fox_and_Box_Accumulation.cpp		A_Fox_and_Box_Accumulation.cpp
A_Free_Cash.cpp		A_Free_Cash.cpp
A_GCD_vs_LCM.cpp		A_GCD_vs_LCM.cpp
A_Game.cpp		A_Game.cpp
A_Game_with_Cards.cpp		A_Game_with_Cards.cpp
A_Gamer_Hemose.cpp		A_Gamer_Hemose.cpp
A_Gift_Carpet.cpp		A_Gift_Carpet.cpp
A_Good_Pairs.cpp		A_Good_Pairs.cpp
A_Grass_Field.cpp		A_Grass_Field.cpp
A_Greatest_Convex.cpp		A_Greatest_Convex.cpp
A_Greg_and_Array.cpp		A_Greg_and_Array.cpp
A_Hall_of_Fame.cpp		A_Hall_of_Fame.cpp
A_Hard_Way.cpp		A_Hard_Way.cpp
A_Hossam_and_Combinatorics.cpp		A_Hossam_and_Combinatorics.cpp
A_Ice_Skating.cpp		A_Ice_Skating.cpp
A_Image.cpp		A_Image.cpp
A_Immobile_Knight.cpp		A_Immobile_Knight.cpp
A_Integer_Diversity.cpp		A_Integer_Diversity.cpp

Repository files navigation

#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define all(x)  begin(x) , end(x)
#define nl      "\n" 

void solve(int& __case__)
{
    int n ; cin >> n ;
    int m ; cin >> m ;

    string str ; cin >> str ;

    vector<int> ones ; 
    vector<int> zeros ; 

    ones.push_back(-1) , zeros.push_back(-1) ;

    for(int i = 0 ; i < n ; i++){
        ( str[i] == '1' ? ones : zeros ).push_back(i);
    }
    // adding n / -1 is amazing trick to handle corrner cases in set (not found cases ) 
    ones.push_back(n) ; zeros.push_back(n) ;
    set<pair<int,int>> s ;

    while (m--){
        int l , r ; cin >> l >> r ;
        l-- ; r-- ;

        int firstOne = *lower_bound(begin(ones),end(ones) , l) ;
        int lastZero = *prev(lower_bound(begin(zeros),end(zeros), r + 1)) ;

        if( firstOne > lastZero ) {
            // 00000011111 ( all sorted )
            s.insert({-1, -1});
        } else {
            s.insert({firstOne,lastZero}) ;
        }

    }
    
    cout << s.size() << nl;
}

signed main()
{   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int testCases = 1 , case_ = 1;     
    cin >> testCases; for (int case_ = 1; case_ <= testCases; case_++) 
        solve(case_);
}