Submission #1084528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084528		peacebringer1667	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	143 ms	44992 KiB

street_lamps

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 3e5 + 5;

struct query{
	int type = 0,v1 = 0,v2 = 0;
};

query Q[maxn];
bool a[maxn];
void input (int n,int q){
	string s;
	cin >> s;
	for (int i = 1 ; i <= n ; i++)
	  a[i] = s[i - 1] - 48;
	
	for (int i = 1 ; i <= q ; i++){
		cin >> s;
		if (s[0] == 't'){
			cin >> Q[i].v1;
			Q[i].type = 1;
		}
		else{
			cin >> Q[i].v1 >> Q[i].v2;
			Q[i].type = 2;
		}
	}
}

namespace sub1{
	bool check(int n,int q){
		return max(n,q) <= 100;
	}
	
	const int N = 105;
	
	bool arr[N][N];
	int pre[N][N];
	
	void prepare(int n,int q){
		for (int i = 1 ; i <= n ; i++)
		  arr[0][i] = a[i];
		  
		for (int id = 1 ; id <= q ; id++){
			for (int i = 1 ; i <= n ; i++)
			  arr[id][i] = arr[id - 1][i];
			
			if (Q[id].type == 1)
			  arr[id][Q[id].v1] ^= 1;
		}
		
		for (int id = 0 ; id <= q ; id++)
			for (int i = 1 ; i <= n ; i++)
			  pre[id][i] = pre[id][i - 1] + arr[id][i];
	}
	
	void solve(int n,int q){
	   prepare(n,q);
	   
	   for (int i = 1 ; i <= q ; i++)
	     if (Q[i].type == 2){
	     	int res = 0,l = Q[i].v1,r = Q[i].v2;
	     	
	     	for (int id = 0 ; id < i ; id++)
	     	  res += (r - l == pre[id][r - 1] - pre[id][l - 1]) ? 1 : 0;
			cout << res << "\n"; 
		 }	
	}
}

namespace sub2{
	bool check(int n,int q){
		for (int i = 1 ; i <= q ; i++)
		  if (Q[i].type == 2 && Q[i].v1 != Q[i].v2 - 1) return 0;
		return 1;
	}
	
	vector <vector<int>> vec(maxn),pre(maxn);
	
	int SOLVE(int p,int cur){
		if (!a[p]) return pre[p].back();
		
		int ans = cur - vec[p].back();
		if (vec[p].size() >= 2)
		  ans += pre[p][pre[p].size() - 2];
		return ans;
	}
	
	void solve(int n,int q){
		for (int i = 1 ; i <= n ; i++){
			vec[i].push_back(0);
			pre[i].push_back(0);
		}
		
		for (int i = 1 ; i <= q ; i++)
		  if (Q[i].type == 1){
		      int p = Q[i].v1;
		      a[p] ^= 1;
			  pre[p].push_back(i - vec[p].back());
			  vec[p].push_back(i); 
			  if (vec[p].size() >= 3)
			    pre[p][pre[p].size() - 1] += pre[p][pre[p].size() - 3];
		  }
		  else cout << SOLVE(Q[i].v1,i) << "\n";
	}
}

namespace sub3{
	const int inf = 1e9;
	
	struct segment_tree{
		int seg[4*maxn];
		
		void init(int n){
			for (int i = 0 ; i <= 4*n + 6 ; i++)
			  seg[i] = inf;
		}
		
		void update(int l,int r,int v,int p,int val){
			if (l > p || r < p) return;
			if (l == r){
				seg[v] = min(seg[v],val);
				return;
			}
			
			int w = (l + r)/2;
			update(l,w,2*v + 1,p,val);
			update(w + 1,r,2*v + 2,p,val);
			seg[v] = min(seg[2*v + 1],seg[2*v + 2]);
		}
		
		int calc(int l,int r,int v,int lx,int rx){
			if (l > rx || r < lx) return inf;
			if (l >= lx && r <= rx) return seg[v];
			
			int w = (l + r)/2;
			return min(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
		}
	} seg;
	int pre[maxn];
	
	int SOLVE(int l,int r,int n,int id){
		if (pre[r - 1] - pre[l - 1] != r - l) return 0;
		
		return min(id,seg.calc(1,n,0,l,r - 1) - 1);
	}
	
	void solve(int n,int q){
		seg.init(n);
		for (int i = 1 ; i <= n ; i++) pre[i] = pre[i - 1] + a[i];
		
		for (int i = 1 ; i <= q ; i++)
		  if (Q[i].type == 1)
		    seg.update(1,n,0,Q[i].v1,i);
		  else cout << SOLVE(Q[i].v1,Q[i].v2,n,i) << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	freopen("LAMB.inp","r",stdin);
//	freopen("LAMB.out","w",stdout);
	int n,q;
	cin >> n >> q;
	input(n,q);
	
	if (sub1::check(n,q)){
		sub1::solve(n,q);
		return 0;
	}
	
	if (sub2::check(n,q)){
		sub2::solve(n,q);
		return 0;
	}
	
	sub3::solve(n,q);

	return 0;
}

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