oj.uz

Submission #1044879

# Submission time Handle Problem Language Result Execution time Memory
1044879 2024-08-05T14:17:18 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 55 ms 9900 KB 
#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define ii pair<long long,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1e15
#define MOD 1000000007
#define MX 200005
using namespace std;



void solve(){
    int n,q; cin >> n >> q;
    string s; cin >> s;
    if(n>100 || q>100){
        int tot[n+1], last[n+1], cur[n+1];
        for(int i=1; i<=n; i++){
            tot[i]=0;
            last[i]=0;
            cur[i]=s[i-1]-'0';
        }
        for(int i=1; i<=q; i++){
            cin >> s;
            if(s[0]=='t'){
                int a; cin >> a;
                if(cur[a]==0){
                    last[a]=i;
                }
                else{
                    tot[a]+=i-last[a];
                }
                cur[a]=1-cur[a];
            }
            else{
                int l,r; cin >> l >> r;
                int ans=tot[l];
                if(cur[l]) ans+=i-last[l];
                cout << ans << endl;
            }
        }
        return;
    }
    int arr[q+1][n+1];
    for(int i=1; i<=n; i++){
        if(s[i-1]=='0') arr[1][i]=0;
        else arr[1][i]=1;
    }
    
    for(int i=1; i<=q; i++){
        string h; cin >> h;
        if(i<q) for(int j=1; j<=n; j++) arr[i+1][j]=arr[i][j];
        if(h[0]=='t'){
            int a; cin >> a;
            arr[i+1][a]=1-arr[i+1][a];
        }
        else{
            int l,r; cin >> l >> r;
            int ans=0;
            for(int j=1; j<=i; j++){
                int ok=1;
                for(int f=l; f<r; f++){
                    if(!arr[j][f]){
                        ok=0;
                        break;
                    }
                }
                if(ok){
                    ans++;
                }
            }
            cout << ans << endl;
        }
    }
}
 
 
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif
 
    /*freopen("nondec.in","r",stdin);
    freopen("nondec.out","w",stdout);*/
 
    int t=1;
    //cin >> t;
    while(t--) solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1360 KB Output is correct
2 Correct 43 ms 1360 KB Output is correct
3 Correct 36 ms 1372 KB Output is correct
4 Correct 47 ms 8520 KB Output is correct
5 Correct 49 ms 8860 KB Output is correct
6 Correct 42 ms 8416 KB Output is correct
7 Correct 52 ms 8512 KB Output is correct
8 Correct 55 ms 9900 KB Output is correct

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 1 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 Correct 41 ms 1360 KB Output is correct
9 Correct 43 ms 1360 KB Output is correct
10 Correct 36 ms 1372 KB Output is correct
11 Correct 47 ms 8520 KB Output is correct
12 Correct 49 ms 8860 KB Output is correct
13 Correct 42 ms 8416 KB Output is correct
14 Correct 52 ms 8512 KB Output is correct
15 Correct 55 ms 9900 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -