Submission #1044986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044986		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	99 ms	42412 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;

#define int int64_t    
#define pb push_back

using lint=__int128_t;

const int lim=200100;
const int mod=1e9+7;

using pii=pair<int,int>;

struct query{
    int t,x,y;
};

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out1","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    query q[m];
    for(int i=0;i<m;i++){
        string t;
        cin>>t;
        if(t=="toggle"){
            q[i].t=0;
        }else{
            q[i].t=1;
        }
        if(q[i].t){
            cin>>q[i].x>>q[i].y;
        }else{
            cin>>q[i].x;
        }
            q[i].x--,q[i].y--;
    }
    if(n<=100&&m<=100){
        int arr[m+1][n];
        for(int i=0;i<n;i++){
            arr[0][i]=s[i]-'0';
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                arr[i+1][j]=arr[i][j];
                if(i&&!q[i-1].t&&q[i-1].x==j){
                    arr[i+1][j]=!arr[i+1][j];
                }
                //cerr<<arr[i+1][j]<<" ";
            }//cerr<<"\n";
            if(q[i].t){
                int cnt=0;
                //cerr<<q[i].x<<" "<<q[i].y<<"\n";
                for(int j=0;j<=i;j++){
                    bool ok=1;
                    for(int k=q[i].x;k<q[i].y;k++){
                        if(!arr[j+1][k]){
                            ok=0;
                            break;
                        }
                    }
                    cnt+=ok;
                }
                cout<<cnt<<"\n";
            }
        }
    }else{
        bool ok=1;
        for(int i=0;i<m;i++){
            if(q[i].t&&q[i].x+1!=q[i].y){
                ok=0;
                break;
            }
        }
        if(ok){
            vector<int>toggles[n];
            for(int i=0;i<n;i++){
                toggles[i].pb(-1);
            }
            vector<int>qr[n];
            for(int i=0;i<m;i++){
                if(!q[i].t)toggles[q[i].x].push_back(i);
                else qr[q[i].x].pb(i);
            }
            int ans[m];
            for(int i=0;i<n;i++){
                int state=s[i]-'0';
                int tp=0,cur=0;
                for(int j=0;j+1<toggles[i].size();j++){
                    while(tp<qr[i].size()&&qr[i][tp]<=toggles[i][j+1]){
                        ans[qr[i][tp]]=cur+state*(qr[i][tp]-toggles[i][j]);
                        assert(0<=qr[i][tp]&&qr[i][tp]<m);
                        tp++;
                    }
                    cur+=state*(toggles[i][j+1]-toggles[i][j]);
                    state=!state;
                }
                while(tp<qr[i].size()){
                    ans[qr[i][tp]]=cur+state*(qr[i][tp]-toggles[i][toggles[i].size()-1]);
                    tp++;
                }
            }
            for(int i=0;i<m;i++){
                if(q[i].t)cout<<ans[i]<<"\n";
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:94:32: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                 for(int j=0;j+1<toggles[i].size();j++){
      |                             ~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:95:29: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                     while(tp<qr[i].size()&&qr[i][tp]<=toggles[i][j+1]){
      |                           ~~^~~~~~~~~~~~~
street_lamps.cpp:103:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                 while(tp<qr[i].size()){
      |                       ~~^~~~~~~~~~~~~

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