Submission #136752

#	Time	Username	Problem	Language	Result	Execution time	Memory
136752		KLPP	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	1879 ms	33388 KiB

street_lamps

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class ST{
  pii arr[1200000];
public:
  void build(int a, int b, int node){
    if(a==b){
      arr[node]=pii(0,0);
      return;
    }
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
    arr[node]=max(arr[2*node],arr[2*node+1]);
  }
  void update(int a, int b, int node, int pos, int val){
    if(pos<a || b<pos)return;
    if(a==b){
      arr[node]=pii(-1,val);
      return;
    }
    int mid=(a+b)/2;
    update(a,mid,2*node,pos,val);
    update(mid+1,b,2*node+1,pos,val);
    arr[node]=max(arr[2*node],arr[2*node+1]);
  }
  pii query(int a, int b, int node, int x, int y){
    if(b<x || y<a)return pii(-10,0);
    if(x<=a && b<=y)return arr[node];
    int mid=(a+b)/2;
    return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
  }
  void print(int a, int b, int node){
    cout<<a<<" "<<b<<" "<<arr[node].first<<" "<<arr[node].second<<endl;
    if(a==b)return;
    int mid=(a+b)/2;
    print(a,mid,2*node);
    print(mid+1,b,2*node+1);
  }
};
int main(){
  int n,q;
  cin>>n>>q;
  string state;
  cin>>state;
  string type[q];
  int queries[q][2];
  rep(i,0,q){
    cin>>type[i];
    if(type[i]=="query"){
      cin>>queries[i][0]>>queries[i][1];
      queries[i][0]--;
      queries[i][1]-=2;
    }else{
      cin>>queries[i][0];
      queries[i][0]--;
    }
  }
  if(n<=100 && q<=100){
    vector<string> V;
    V.push_back(state);
    rep(i,0,q){
      
      if(type[i]=="query"){
	int ans=0;
	trav(a,V){
	  bool b=true;
	  rep(j,queries[i][0],queries[i][1]+1){
	    if(a[j]=='0')b=false;
	  }
	  ans+=b;
	  //cout<<a<<endl;
	}
	cout<<ans<<endl;
      }else{
	state[queries[i][0]]='0'+'1'-state[queries[i][0]];
      }
      V.push_back(state);
    }
    return 0;
  }
  bool tight=true;
  rep(i,0,q){
    if(type[i]=="query"){
      if(queries[i][1]!=queries[i][0])tight=false;
    }
  }
  if(tight){
    lld times[n];
    lld tot[n];
    rep(i,0,n){
      if(state[i]=='0')times[i]=-1;
      else times[i]=0;
      tot[i]=0;
    }
    rep(i,0,q){
      int l=queries[i][0];
      if(type[i]=="query"){
	lld ans=tot[l];
	if(times[l]!=-1){
	  ans+=i+1-times[l];
	}
	cout<<ans<<endl;
      }else{
	if(times[l]==-1){
	  times[l]=i+1;
	}else{
	  tot[l]+=i+1-times[l];
	  times[l]=-1;
	}
      }
    }
    return 0;
  }
  ST *S=new ST();
  S->build(0,n-1,1);
  rep(i,0,n){
    if(state[i]=='1')S->update(0,n-1,1,i,0);
  }
  //S->print(0,n-1,1);
  rep(i,0,q){
    if(type[i]=="toggle"){
      S->update(0,n-1,1,queries[i][0],i+1);
    }else{
      int q=(S->query(0,n-1,1,queries[i][0],queries[i][1]).second-i-1)*S->query(0,n-1,1,queries[i][0],queries[i][1]).first;
      cout<<q<<endl;
      //cout<<S->query(0,n-1,1,queries[i][0],queries[i][1]).first<<" "<<S->query(0,n-1,1,queries[i][0],queries[i][1]).second<<endl;
    }
    //S->print(0,n-1,1);
  }
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20