oj.uz

Submission #1044946

# Submission time Handle Problem Language Result Execution time Memory
1044946 2024-08-05T14:57:49 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 39 ms 21564 KB 
#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(".out","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(0);
            }
            vector<int>qr[n];
            for(int i=0;i<m;i++){
                if(!q[i].x)toggles[q[i].x].push_back(i);
                else qr[q[i].x].pb(i);
            }
            int ans[n];
            for(int i=0;i<n;i++){
                int state=s[i]-'0';
                int tp=0,cur=0;
                for(int j=0;j<toggles[i].size()-1;j++){
                    while(tp<qr[i].size()&&qr[i][tp]<=toggles[i][j+1]){
                        ans[qr[i][tp]]=cur+state*(i-toggles[i][j]);
                        tp++;
                    }
                    cur+=state*(toggles[i][j+1]-toggles[i][j]);
                    state=!state;
                }
                while(tp<qr[i].size()){
                    ans[qr[i][tp]]=cur+state*(i-toggles[i][toggles[i].size()-1]);
                    tp++;
                }
            }
            for(int i=0;i<m;i++){
                cout<<ans[i]<<"\n";
            }
        }
    }
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:94:30: 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<toggles[i].size()-1;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:102: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]
  102 |                 while(tp<qr[i].size()){
      |                       ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 21564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 39 ms 21564 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -