oj.uz

Submission #136675

# Submission time Handle Problem Language Result Execution time Memory
136675 2019-07-26T06:56:24 Z KLPP Street Lamps (APIO19_street_lamps) C++14
40 / 100
 1748 ms 39420 KB 
#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;
  }
  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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 782 ms 34640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19192 KB Output is correct
2 Correct 24 ms 19192 KB Output is correct
3 Correct 21 ms 19192 KB Output is correct
4 Correct 23 ms 19192 KB Output is correct
5 Correct 516 ms 35604 KB Output is correct
6 Correct 901 ms 36420 KB Output is correct
7 Correct 1273 ms 37044 KB Output is correct
8 Correct 1748 ms 39420 KB Output is correct
9 Correct 1002 ms 32368 KB Output is correct
10 Correct 1135 ms 33656 KB Output is correct
11 Correct 1098 ms 33912 KB Output is correct
12 Correct 1672 ms 38080 KB Output is correct
13 Correct 1736 ms 39332 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19196 KB Output is correct
2 Incorrect 21 ms 19192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Incorrect 782 ms 34640 KB Output isn't correct
9 Halted 0 ms 0 KB -