oj.uz

Submission #1084528

# Submission time Handle Problem Language Result Execution time Memory
1084528 2024-09-06T11:10:01 Z peacebringer1667 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 143 ms 44992 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 + 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 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 7 ms 14428 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23892 KB Output is correct
2 Correct 52 ms 24296 KB Output is correct
3 Correct 61 ms 25132 KB Output is correct
4 Correct 131 ms 42920 KB Output is correct
5 Correct 143 ms 43456 KB Output is correct
6 Correct 122 ms 42684 KB Output is correct
7 Correct 121 ms 43452 KB Output is correct
8 Correct 128 ms 44992 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Incorrect 6 ms 14648 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 Incorrect 5 ms 14428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 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 7 ms 14428 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 51 ms 23892 KB Output is correct
9 Correct 52 ms 24296 KB Output is correct
10 Correct 61 ms 25132 KB Output is correct
11 Correct 131 ms 42920 KB Output is correct
12 Correct 143 ms 43456 KB Output is correct
13 Correct 122 ms 42684 KB Output is correct
14 Correct 121 ms 43452 KB Output is correct
15 Correct 128 ms 44992 KB Output is correct
16 Correct 7 ms 14424 KB Output is correct
17 Incorrect 6 ms 14648 KB Output isn't correct
18 Halted 0 ms 0 KB -