oj.uz

Submission #266691

# Submission time Handle Problem Language Result Execution time Memory
266691 2020-08-15T12:15:29 Z define Street Lamps (APIO19_street_lamps) C++17
20 / 100
 4692 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.tie(0);ios::sync_with_stdio(false);
	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 12 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 1187 ms 41912 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 13 ms 16896 KB Output is correct
2 Correct 14 ms 16896 KB Output is correct
3 Correct 15 ms 16896 KB Output is correct
4 Correct 16 ms 16896 KB Output is correct
5 Correct 3745 ms 44396 KB Output is correct
6 Correct 4518 ms 52444 KB Output is correct
7 Correct 4692 ms 52360 KB Output is correct
8 Correct 4424 ms 66860 KB Output is correct
9 Correct 1436 ms 39160 KB Output is correct
10 Correct 1601 ms 40384 KB Output is correct
11 Correct 1566 ms 42360 KB Output is correct
12 Correct 4610 ms 52520 KB Output is correct
13 Correct 4144 ms 72776 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16896 KB Output is correct
2 Incorrect 14 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 12 ms 16768 KB Output isn't correct
2 Halted 0 ms 0 KB -