oj.uz

Submission #440519

# Submission time Handle Problem Language Result Execution time Memory
440519 2021-07-02T11:12:58 Z KULIKOLD Street Lamps (APIO19_street_lamps) C++17
40 / 100
 130 ms 8336 KB 
//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int DIM = 3E5+7;
int n,q;
int A[DIM];
struct node{
    int type,a,b;
} Q[DIM];
const int SZ = 107;
vector<node> V[SZ];
int ans[DIM];
void solve(){
    for(int i = q;i>=1;--i){
        V[i] = V[i+1];
        if (Q[i].type==1)
            V[i].push_back({i,Q[i].a,Q[i].b});
    }
    for(int i = 1;i<=q;++i){
        for(auto to:V[i]){
            ll flag = 0;
            for(int j = to.a;j<to.b;++j){
                if (!A[j]){
                    flag = 1;
                    break;
                }
            }
            if (!flag)
                ans[to.type]++;
        }
        if (Q[i].type==0)
            A[Q[i].a]^=1;

        if (Q[i].type)
        cout<<ans[i]<<endl;
    }

}
int last[DIM],sum[DIM];
void solve1(){

    for(int i = 1;i<=q;++i){
        if (Q[i].type==1){
            cout<<(i-last[Q[i].a])*A[Q[i].a]+sum[Q[i].a]<<endl;
        }
        else{
            sum[Q[i].a]+=(i-last[Q[i].a])*A[Q[i].a];
            last[Q[i].a] = i;
            A[Q[i].a]^=1;
        }
    }
}
int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i<=n;++i){
        char ch;
        cin>>ch;
        A[i] = int(ch-'0');
    }
    int flag = 0;
    for(int i = 1;i<=q;++i){
        string s;
        cin>>s;
        Q[i].type = (s=="query");
        if (Q[i].type==1) {
            cin >> Q[i].a >> Q[i].b;
            if (Q[i].b-Q[i].a!=1)
                flag = 1;
        }
        else cin>>Q[i].a;
    }
    if (n<=100 && q<=100)
        solve();
    else if (flag==0)
        solve1();
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 4728 KB Output is correct
2 Correct 90 ms 4768 KB Output is correct
3 Correct 91 ms 4828 KB Output is correct
4 Correct 111 ms 7956 KB Output is correct
5 Correct 117 ms 8336 KB Output is correct
6 Correct 97 ms 7956 KB Output is correct
7 Correct 128 ms 5584 KB Output is correct
8 Correct 130 ms 6904 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 332 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 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 91 ms 4728 KB Output is correct
9 Correct 90 ms 4768 KB Output is correct
10 Correct 91 ms 4828 KB Output is correct
11 Correct 111 ms 7956 KB Output is correct
12 Correct 117 ms 8336 KB Output is correct
13 Correct 97 ms 7956 KB Output is correct
14 Correct 128 ms 5584 KB Output is correct
15 Correct 130 ms 6904 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -