GitHub - Sayemahamed/cpp

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 302 Commits
.cph		.cph
.vscode		.vscode
0Templet0.cpp		0Templet0.cpp
1.cpp		1.cpp
11.cpp		11.cpp
1_Guess_the_Number.cpp		1_Guess_the_Number.cpp
1ll1.cpp		1ll1.cpp
2.cpp		2.cpp
A_-_Firefly.cpp		A_-_Firefly.cpp
A_-_Integer_Sum.cpp		A_-_Integer_Sum.cpp
A_-_Restoring_the_Duration_of_Tasks.cpp		A_-_Restoring_the_Duration_of_Tasks.cpp
A_-_Rightmost.cpp		A_-_Rightmost.cpp
A_-_Sets-STL.cpp		A_-_Sets-STL.cpp
A_1_Make_Nonzero_Sum_easy_version.cpp		A_1_Make_Nonzero_Sum_easy_version.cpp
A_1_Non-alternating_Deck_easy_version.cpp		A_1_Non-alternating_Deck_easy_version.cpp
A_2_-_3_Moves.cpp		A_2_-_3_Moves.cpp
A_2_Alternating_Deck_hard_version.cpp		A_2_Alternating_Deck_hard_version.cpp
A_A_B.cpp		A_A_B.cpp
A_A_characteristic.cpp		A_A_characteristic.cpp
A_Add_Plus_Minus_Sign.cpp		A_Add_Plus_Minus_Sign.cpp
A_Almost_Prime.cpp		A_Almost_Prime.cpp
A_Alyona_and_Numbers.cpp		A_Alyona_and_Numbers.cpp
A_Another_String_Minimization_Problem.cpp		A_Another_String_Minimization_Problem.cpp
A_Anton_and_Danik.cpp		A_Anton_and_Danik.cpp
A_Anton_and_Letters.cpp		A_Anton_and_Letters.cpp
A_Anton_and_Polyhedrons.cpp		A_Anton_and_Polyhedrons.cpp
A_Army.cpp		A_Army.cpp
A_Arpa_s_hard_exam_and_Mehrdad_s_naive_cheat.cpp		A_Arpa_s_hard_exam_and_Mehrdad_s_naive_cheat.cpp
A_Array_Coloring.cpp		A_Array_Coloring.cpp
A_Arrival_of_the_General.cpp		A_Arrival_of_the_General.cpp
A_Balanced_Rating_Changes.cpp		A_Balanced_Rating_Changes.cpp
A_Bear_and_Big_Brother.cpp		A_Bear_and_Big_Brother.cpp
A_Beautiful_Matrix.cpp		A_Beautiful_Matrix.cpp
A_Beautiful_Year.cpp		A_Beautiful_Year.cpp
A_Binary_Protocol.cpp		A_Binary_Protocol.cpp
A_Binary_Search.cpp		A_Binary_Search.cpp
A_Bit.cpp		A_Bit.cpp
A_Black_Square.cpp		A_Black_Square.cpp
A_Boredom.cpp		A_Boredom.cpp
A_Borya_s_Diagnosis.cpp		A_Borya_s_Diagnosis.cpp
A_BowWow_and_the_Timetable.cpp		A_BowWow_and_the_Timetable.cpp
A_Boy_or_Girl.cpp		A_Boy_or_Girl.cpp
A_Brain_s_Photos.cpp		A_Brain_s_Photos.cpp
A_Buy_a_Shovel.cpp		A_Buy_a_Shovel.cpp
A_Calculating_Function.cpp		A_Calculating_Function.cpp
A_Candy_Bags.cpp		A_Candy_Bags.cpp
A_Carrot_Cakes.cpp		A_Carrot_Cakes.cpp
A_Cheap_Travel.cpp		A_Cheap_Travel.cpp
A_Chess_Tourney.cpp		A_Chess_Tourney.cpp
A_Chewand_Number.cpp		A_Chewand_Number.cpp
A_Choosing_Teams.cpp		A_Choosing_Teams.cpp
A_Chord.cpp		A_Chord.cpp
A_Cinema_Line.cpp		A_Cinema_Line.cpp
A_Codeforces_Checking.cpp		A_Codeforces_Checking.cpp
A_Colorful_Stones_Simplified_Edition.cpp		A_Colorful_Stones_Simplified_Edition.cpp
A_Compare_T-Shirt_Sizes.cpp		A_Compare_T-Shirt_Sizes.cpp
A_Computer_Game.cpp		A_Computer_Game.cpp
A_Constructive_Problem.cpp		A_Constructive_Problem.cpp
A_Cookies.cpp		A_Cookies.cpp
A_Counterexample.cpp		A_Counterexample.cpp
A_Counting_Kangaroos_is_Fun.cpp		A_Counting_Kangaroos_is_Fun.cpp
A_Cut_Ribbon.cpp		A_Cut_Ribbon.cpp
A_Cut_the_Triangle.cpp		A_Cut_the_Triangle.cpp
A_DZY_Loves_Chessboard.cpp		A_DZY_Loves_Chessboard.cpp
A_Dalton_the_Teacher.cpp		A_Dalton_the_Teacher.cpp
A_Deadline.cpp		A_Deadline.cpp
A_Desorting.cpp		A_Desorting.cpp
A_Di_visible_Confusion.cpp		A_Di_visible_Confusion.cpp
A_Dice_Tower.cpp		A_Dice_Tower.cpp
A_Die_Roll.cpp		A_Die_Roll.cpp
A_Dima_and_Friends.cpp		A_Dima_and_Friends.cpp
A_Diplomas_and_Certificates.cpp		A_Diplomas_and_Certificates.cpp
A_Directional_Increase.cpp		A_Directional_Increase.cpp
A_Divide_and_Conquer.cpp		A_Divide_and_Conquer.cpp
A_Don_t_Try_to_Count.cpp		A_Don_t_Try_to_Count.cpp
A_Double_Cola.cpp		A_Double_Cola.cpp
A_Dragons.cpp		A_Dragons.cpp
A_Dreamoon_and_Stairs.cpp		A_Dreamoon_and_Stairs.cpp
A_Dreamoon_and_WiFi.cpp		A_Dreamoon_and_WiFi.cpp
A_Dubstep.cpp		A_Dubstep.cpp
A_Dungeon.cpp		A_Dungeon.cpp
A_Echo.cpp		A_Echo.cpp
A_Escalator_Conversations.cpp		A_Escalator_Conversations.cpp
A_Escape_from_Stones.cpp		A_Escape_from_Stones.cpp
A_Eugeny_and_Array.cpp		A_Eugeny_and_Array.cpp
A_Even_Odds.cpp		A_Even_Odds.cpp
A_Fancy_Fence.cpp		A_Fancy_Fence.cpp
A_Favorite_Sequence.cpp		A_Favorite_Sequence.cpp
A_Flipping_Game.cpp		A_Flipping_Game.cpp
A_Football.cpp		A_Football.cpp
A_Forbidden_Integer.cpp		A_Forbidden_Integer.cpp
A_Fox_And_Snake.cpp		A_Fox_And_Snake.cpp
A_Fox_and_Box_Accumulation.cpp		A_Fox_and_Box_Accumulation.cpp
A_Free_Cash.cpp		A_Free_Cash.cpp
A_Free_Ice_Cream.cpp		A_Free_Ice_Cream.cpp
A_Frog_1.cpp		A_Frog_1.cpp
A_Games.cpp		A_Games.cpp
A_Garland.cpp		A_Garland.cpp
A_George_and_Accommodation.cpp		A_George_and_Accommodation.cpp
A_Gift_Carpet.cpp		A_Gift_Carpet.cpp

Repository files navigation

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    string s;
    cin >> n >> m >> s;

    vector<int> lf( n ), rg( n );
    lf[ 0 ] = -1;
    for (int i = 0; i < n; ++i) {
        if (i > 0) lf[ i ] = lf[ i - 1 ];
        if (s[ i ] == '0') lf[ i ] = i;
    }
    rg[ n - 1 ] = n;
    for (int i = n - 1; i >= 0; --i) {
        if (i + 1 < n) rg[ i ] = rg[ i + 1 ];
        if (s[ i ] == '1') rg[ i ] = i;
    }

    set<pair<int, int>> st;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        int ll = rg[ l - 1 ], rr = lf[ r - 1 ];
        if (ll > rr) {
            st.insert( { -1, -1 } );
        }
        else {
            st.insert( { ll, rr } );
        }
    }

    cout << st.size() << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}