Submission #976906

#	Time	Username	Problem	Language	Result	Execution time	Memory
976906		AIF_is_carving	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	139 ms	25064 KiB

street_lamps

#include<bits/stdc++.h>
 
typedef long long ll;
using namespace std;

// struct Interval {
//     ll s, e;
// };

// // Function used in sort
// bool mycomp(Interval a, Interval b) { return a.s < b.s; }

// void mergeIntervals(Interval arr[], ll n)
// {
//     // Sort Intervals in increasing order of
//     // start time
//     sort(arr, arr + n, mycomp);

//     ll index = 0; // Stores index of last element
//     // in output array (modified arr[])

//     // Traverse all input Intervals
//     for (ll i = 1; i < n; i++) {
//         // If this is not first Interval and overlaps
//         // with the previous one
//         if (arr[index].e >= arr[i].s) {
//             // Merge previous and current Intervals
//             arr[index].e = max(arr[index].e, arr[i].e);
//         }
//         else {
//             index++;
//             arr[index] = arr[i];
//         }
//     }

//     // Now arr[0..index-1] stores the merged Intervals
//     //cout << "\n The Merged Intervals are: ";
//     ll ans =0;
//     for (ll i = 0; i <= index; i++) ans+= arr[i].e-arr[i].s+1;

//         cout<<ans<<"\n";
//         //cout << "[" << arr[i].s << ", " << arr[i].e << "] ";
// }

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; cin>>n>>q;
    string str;
    cin>>str;

    vector<int> v[n];
    for(int i=0; i<n; i++){
        if(str[i] =='1') v[i].push_back(0);
    }

    for(int i=1; i<=q; i++){
        string mark;
        cin>>mark;
        if(mark == "toggle"){
            int indx;
            cin>>indx;

            if(str[indx-1] == '1') str[indx-1]='0';

            v[indx-1].push_back(i);
            
        }
        else{
            int l, r; cin>>l>>r;

            l-=1;

            if(v[l].size()%2 == 0){
                int ans =0;
                for(int j=0; j<v[l].size(); j+=2){
                    ans+=v[l][j+1]-v[l][j];
                }

                cout<<ans<<"\n";
                if(ans>0){
                    v[l].clear();
                    v[l].push_back(i-ans);
                    v[l].push_back(i);
                }
            }
            else{
                int ans =0;
                for(int j=0; j<v[l].size()-1; j+=2){
                    ans+=v[l][j+1]-v[l][j];
                }
                //cout<<i<<" "<<v[l][v[l].size()-1];
                ans += i-v[l][v[l].size()-1];
                cout<<ans<<"\n";
                if(ans>0){
                    v[l].clear();
                    v[l].push_back(i-ans);
                }
            }
        }
    }

    return 0;
}
 

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:77:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 for(int j=0; j<v[l].size(); j+=2){
      |                              ~^~~~~~~~~~~~
street_lamps.cpp:90:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 for(int j=0; j<v[l].size()-1; j+=2){
      |                              ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20