Submission #1045004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045004		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	104 ms	41956 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=300100;
const int mod=1e9+7;

using pii=pair<int,int>;

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

struct{
    int tree[4*lim];
    int n;
    void init(int N){
        n=N;
        for(int i=0;i<=4*n;i++)tree[i]=LLONG_MAX;
    }
    int P,VAL;
    void update(int l,int r,int node){
        if(l==r){
            tree[node]=VAL;
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
        tree[node]=max(tree[child],tree[child|1]);
    }
    void update(int p,int val){
        P=p,VAL=val;
        update(0,n-1,1);
    }
    int L,R;
    int query(int l,int r,int node){
        if(L<=l&&r<=R){
            return tree[node];
        }
        if(r<L||R<l){
            return -5;
        }
        int mid=(l+r)>>1,child=node<<1;
        return max(query(l,mid,child),query(mid+1,r,child|1));
    }
    int query(int l,int r){
        L=l,R=r;
        return query(0,n-1,1);
    }
}st;

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";
            }
        }else{
                st.init(n);
            for(int i=0;i<n;i++){
                if(s[i]=='1')st.update(i,-1);
            }
            for(int i=0;i<m;i++){
                if(q[i].t){
                    int val=st.query(q[i].x,q[i].y);
                    if(val!=LLONG_MAX){
                        cout<<i-val<<"\n";
                    }else{
                        cout<<"0\n";
                    }
                }else{
                    st.update(q[i].x,i);
                }
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:133: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]
  133 |                 for(int j=0;j+1<toggles[i].size();j++){
      |                             ~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:134: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]
  134 |                     while(tp<qr[i].size()&&qr[i][tp]<=toggles[i][j+1]){
      |                           ~~^~~~~~~~~~~~~
street_lamps.cpp:142: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]
  142 |                 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