oj.uz

답안 #1087071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087071 2024-09-12T07:26:50 Z alexander707070 가로등 (APIO19_street_lamps) C++14
20 / 100
 57 ms 20512 KB 
#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

struct ST{
    int tree[4*MAXN],tree2[4*MAXN];

    void update(int v,int l,int r,int pos,int val){
        if(l==r){
            tree[v]=tree2[v]=val;
        }else{
            int tt=(l+r)/2;
            if(pos<=tt)update(2*v,l,tt,pos,val);
            else update(2*v+1,tt+1,r,pos,val);

            tree[v]=min(tree[2*v],tree[2*v+1]);
            tree2[v]=max(tree2[2*v],tree2[2*v+1]);
        }
    }

    int getmin(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 1;
        if(l==ll and r==rr){
            return tree[v];
        }else{
            int tt=(l+r)/2;
            return min( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
        }
    }

    int getmax(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr){
            return tree2[v];
        }else{
            int tt=(l+r)/2;
            return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
        }
    }
}st;

int n,q,tim,x,l,r;
char c[MAXN];
int last[MAXN],sum[MAXN];
string type;

int d[107][107];

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q>>(c+1);
    for(int i=1;i<=n;i++){
        if(c[i]=='1')st.update(1,1,n,i,1);

        d[0][i]=c[i];
    }

    for(int i=1;i<=q;i++){
        cin>>type;
        if(type=="toggle"){
            cin>>x;
            if(c[x]=='0'){
                c[x]='1'; last[x]=i;
                st.update(1,1,n,x,i+1);
            }else{
                c[x]='0'; sum[x]+=i-last[x];
            }
        }else{
            cin>>l>>r;

            if(q<=100){
                int res=0;
                for(int f=0;f<i;f++){
                    for(int k=l;k<r;k++){
                        if(d[f][k]=='0')break;
                        else if(k==r-1)res++;
                    }
                }
                cout<<res<<"\n";
            }else if(l+1<r){
                int s=st.getmin(1,1,n,l,r-1);
                if(s==0)cout<<0<<"\n";
                else cout<<i+1-st.getmax(1,1,n,l,r-1)<<"\n";
            }else{
                if(c[l]=='0')cout<<sum[l]<<"\n";
                else cout<<sum[l]+i-last[l]<<"\n";
            }
        }

        if(n<=100 and q<=100){
            for(int f=1;f<=n;f++)d[i][f]=c[f];
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 4564 KB Output is correct
2 Correct 57 ms 4952 KB Output is correct
3 Correct 54 ms 5244 KB Output is correct
4 Runtime error 24 ms 20512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 13 ms 18780 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 47 ms 4564 KB Output is correct
9 Correct 57 ms 4952 KB Output is correct
10 Correct 54 ms 5244 KB Output is correct
11 Runtime error 24 ms 20512 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -