oj.uz

Submission #440524

# Submission time Handle Problem Language Result Execution time Memory
440524 2021-07-02T11:20:10 Z KULIKOLD Street Lamps (APIO19_street_lamps) C++17
60 / 100
 295 ms 17092 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 tt[DIM],T[DIM*4];
const int INF = 1E9;
void buildtree(int t,int tl,int tr){
    if (tl==tr){
        T[t] = tt[tl];
        return;
    }
    int tm = (tl+tr)/2;
    buildtree(t*2+1,tl,tm);
    buildtree(t*2+2,tm+1,tr);
    T[t] = max(T[t*2+1],T[t*2+2]);
}
int query(int t,int tl,int tr,int l,int r){
    if (tl>r || l>tr)
        return 0;
    if (l<=tl && tr<=r)
        return T[t];
    int tm = (tl+tr)/2;
    return max(query(t*2+1,tl,tm,l,r),query(t*2+2,tm+1,tr,l,r));
}
void solve2(){
    for(int i = 1;i<=n;++i){
        if (!A[i])
            tt[i] = INF;
    }
    for(int i = 1;i<=q;++i){
        if (Q[i].type==0)
            tt[Q[i].a] = i;
    }
    buildtree(0,1,n);
    for(int i = 1;i<=q;++i){
        if (Q[i].type==1){
            cout<<max(0,i-query(0,1,n,Q[i].a,Q[i].b-1))<<endl;
        }
    }
}
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,flag1 = 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 (Q[i].type==0)
            if (A[Q[i].a])
                flag1 = 1;
    }
    if (n<=100 && q<=100)
        solve();
    else if (flag==0)
        solve1();
    else if (flag1==0)
        solve2();
    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 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 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 85 ms 4792 KB Output is correct
2 Correct 86 ms 4784 KB Output is correct
3 Correct 91 ms 4744 KB Output is correct
4 Correct 108 ms 8028 KB Output is correct
5 Correct 119 ms 8500 KB Output is correct
6 Correct 115 ms 8000 KB Output is correct
7 Correct 128 ms 5572 KB Output is correct
8 Correct 132 ms 6940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 80 ms 14524 KB Output is correct
6 Correct 143 ms 15184 KB Output is correct
7 Correct 212 ms 15924 KB Output is correct
8 Correct 290 ms 17064 KB Output is correct
9 Correct 109 ms 6852 KB Output is correct
10 Correct 129 ms 7368 KB Output is correct
11 Correct 124 ms 7684 KB Output is correct
12 Correct 282 ms 16764 KB Output is correct
13 Correct 295 ms 17092 KB Output is correct

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 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 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 85 ms 4792 KB Output is correct
9 Correct 86 ms 4784 KB Output is correct
10 Correct 91 ms 4744 KB Output is correct
11 Correct 108 ms 8028 KB Output is correct
12 Correct 119 ms 8500 KB Output is correct
13 Correct 115 ms 8000 KB Output is correct
14 Correct 128 ms 5572 KB Output is correct
15 Correct 132 ms 6940 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 80 ms 14524 KB Output is correct
21 Correct 143 ms 15184 KB Output is correct
22 Correct 212 ms 15924 KB Output is correct
23 Correct 290 ms 17064 KB Output is correct
24 Correct 109 ms 6852 KB Output is correct
25 Correct 129 ms 7368 KB Output is correct
26 Correct 124 ms 7684 KB Output is correct
27 Correct 282 ms 16764 KB Output is correct
28 Correct 295 ms 17092 KB Output is correct
29 Incorrect 1 ms 332 KB Output isn't correct
30 Halted 0 ms 0 KB -