oj.uz

Submission #1084513

# Submission time Handle Problem Language Result Execution time Memory
1084513 2024-09-06T10:53:07 Z peacebringer1667 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 187 ms 44900 KB 
#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 + 1 ; 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));
	}
	
	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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 9 ms 14428 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Correct 7 ms 14684 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 23808 KB Output is correct
2 Correct 53 ms 24144 KB Output is correct
3 Correct 62 ms 24988 KB Output is correct
4 Correct 187 ms 42836 KB Output is correct
5 Correct 166 ms 43388 KB Output is correct
6 Correct 162 ms 42636 KB Output is correct
7 Correct 154 ms 43456 KB Output is correct
8 Correct 145 ms 44900 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Incorrect 6 ms 14428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Incorrect 10 ms 14432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 9 ms 14428 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Correct 7 ms 14684 KB Output is correct
8 Correct 54 ms 23808 KB Output is correct
9 Correct 53 ms 24144 KB Output is correct
10 Correct 62 ms 24988 KB Output is correct
11 Correct 187 ms 42836 KB Output is correct
12 Correct 166 ms 43388 KB Output is correct
13 Correct 162 ms 42636 KB Output is correct
14 Correct 154 ms 43456 KB Output is correct
15 Correct 145 ms 44900 KB Output is correct
16 Correct 6 ms 14424 KB Output is correct
17 Incorrect 6 ms 14428 KB Output isn't correct
18 Halted 0 ms 0 KB -