oj.uz

Submission #266689

# Submission time Handle Problem Language Result Execution time Memory
266689 2020-08-15T12:14:18 Z define Street Lamps (APIO19_street_lamps) C++17
0 / 100
 5000 ms 72776 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};
auto f=[](int a,int b){return a+b;};
auto g=[](int a,int b,int sz){return b;};
auto h=[](int a,int b){return b;};
int N,Q;
string S;
string s[300005];
int A[300005],B[300005];
int ok[300005],ng[300005];
signed main(){
	cin>>N>>Q>>S;
	REP(i,Q+1){
		cin>>s[i];
		if(s[i]=="query"){
			cin>>A[i]>>B[i];A[i]--;B[i]--;
			ok[i]=i;
			ng[i]=-1;
		}else {
			cin>>A[i];A[i]--;
		}
	}
	vector<int>kouho[300005];
	while(1){
		bool flag=false;
		rep(i,Q+1)kouho[i].clear();
		REP(i,Q+1){
			if(s[i]=="query"&&ok[i]-ng[i]>1){
				flag=true;
				kouho[(ok[i]+ng[i])/2].push_back(i);
			}
		}
		if(!flag)break;
		Segtree<int,int,decltype(f),decltype(g),decltype(h)>segtree(N,f,g,h,0,-1);
		rep(i,N)if(S[i]=='0')segtree.set(i,1);
		segtree.init();
		rep(i,Q+1){
			if(s[i]=="toggle"){
				segtree.update(A[i],A[i]+1,0);
			}
			for(int j:kouho[i]){
				if(segtree.query(A[j],B[j])==0)ok[j]=i;
				else ng[j]=i;
			}
		}
	}
	REP(i,Q+1){
		if(s[i]=="query")cout<<i-ok[i]<<endl;
	}
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16896 KB Output is correct
2 Correct 16 ms 16896 KB Output is correct
3 Correct 17 ms 16896 KB Output is correct
4 Correct 19 ms 16896 KB Output is correct
5 Correct 4027 ms 48780 KB Output is correct
6 Correct 4664 ms 57216 KB Output is correct
7 Correct 4795 ms 57620 KB Output is correct
8 Correct 4949 ms 72776 KB Output is correct
9 Correct 1578 ms 41976 KB Output is correct
10 Correct 1759 ms 43384 KB Output is correct
11 Correct 1814 ms 45304 KB Output is correct
12 Execution timed out 5061 ms 58316 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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