oj.uz

Submission #733341

# Submission time Handle Problem Language Result Execution time Memory
733341 2023-04-30T13:58:40 Z minhcool Street Lamps (APIO19_street_lamps) C++17
40 / 100
 264 ms 14424 KB 
#include<bits/stdc++.h>
using namespace std;
 
// 60 is enough for gold lol, we got 2 ACs already
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, q;
string s;
vector<pair<int, ii>> queries;
 
namespace solve_small{
	bool ck[105][105];
	void process(){
		for(int i = 1; i <= n; i++) ck[1][i] = (s[i - 1] != '0');
		for(int i = 1; i <= q; i++){
			for(int j = 1; j <= n; j++) ck[i + 1][j] = ck[i][j];
			if(queries[i - 1].fi == 1) ck[i + 1][queries[i - 1].se.fi] ^= 1;
			else{
				int ans = 0;
				for(int j = 1; j <= i; j++){
					int ckk = 1;
					for(int k = queries[i - 1].se.fi; k <= queries[i - 1].se.se; k++) ckk &= ck[j][k];
					ans += ckk;
				}
				cout << ans << "\n";
			}
		//	for(int j = 1; j <= n; j++) cout << ck[i][j];
			//cout << "\n";
		}
	}
}
 
namespace solve_eq{
	int lst[N];
	int tol_off[N];
	void process(){
		for(int i = 1; i <= n; i++) lst[i] = tol_off[i] = 0;
		for(int i = 1; i <= n; i++) if(s[i - 1] == '1') lst[i] = oo;
		for(int i = 1; i <= q; i++){
			if(queries[i - 1].fi == 1){
				if(s[queries[i - 1].se.fi - 1] == '0'){
					tol_off[queries[i - 1].se.fi] += i - lst[queries[i - 1].se.fi];
					lst[queries[i - 1].se.fi] = oo;
					s[queries[i - 1].se.fi - 1] = '1';
				}
				else{
					lst[queries[i - 1].se.fi] = i;
					s[queries[i - 1].se.fi - 1] = '0';
				}
			}
			else{
				int temp = tol_off[queries[i - 1].se.fi];
				temp += max(0LL, i - lst[queries[i - 1].se.fi]);
				cout << (i - temp) << "\n";
			}
		}
	}
}
 
namespace off_solve{
	vector<iii> ques[33];
	bool cmp(iii a, iii b){
		return ((a.fi.fi + a.fi.se) < (b.fi.fi + b.fi.se));
	}
	int bit[N], ans[N];
	void upd(int id, int val){
		for(; id <= n; id += id & -id) bit[id] += val;
	}
	int get(int id){
		int ans = 0;
		for(; id; id -= id & -id) ans += bit[id];
		return ans;
	}
	void process(){
		for(int i = 0; i < q; i++){
			if(queries[i].fi == 2) ques[0].pb({{-1, q - 1}, i});
		}
		for(int i = 0; i <= 30; i++){
			if(!ques[i].size()) break;
			//cout << i << " " << ques[i].size() << "\n";
			sort(ques[i].begin(), ques[i].end(), cmp);
			int temp = -1;
			for(int j = 1; j <= n; j++) bit[j] = 0;
			for(int j = 1; j <= n; j++) if(s[j - 1] == '0') upd(j, 1);
			for(auto it : ques[i]){
				int mid = (it.fi.fi + it.fi.se + 1) / 2;
				while(temp < mid){
				//	cout << temp << " " << mid << "\n";
					temp++;
					if(queries[temp].fi == 1) upd(queries[temp].se.fi, 1);
				}
				if(it.fi.fi == it.fi.se){
					ans[it.se] = it.fi.fi;
					continue;
				}
				else{
					int l = queries[it.se].se.fi, r = queries[it.se].se.se;
					if(get(r) != get(l - 1)) ques[i + 1].pb({{it.fi.fi, mid - 1}, it.se});
					else ques[i + 1].pb({{mid, it.fi.se}, it.se});
				}
			}
		}
		for(int j = 0; j < q; j++){
			if(queries[j].fi == 2) cout << min(j + 1, ans[j] + 1) << "\n";
		}
	}
}
 
void process(){
	cin >> n >> q;
	cin >> s;
	bool ck = 1;
	for(int i = 1; i <= q; i++){
		int type;
		string ss;
		cin >> ss;
		type = (ss == "toggle" ? 1 : 2);
		if(type == 1){
			int a;
			cin >> a;
			queries.pb({type, {a, -1}});
		}
		else{
			int a, b;
			cin >> a >> b;
			b--;
			ck &= (a == b);
			queries.pb({type, {a, b}});
		}
	}
	if(n <= 100 && q <= 100) solve_small::process();
	else if(ck) solve_eq::process();
	else off_solve::process();
}
 
signed main(){
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	process();
}
 
/*
5 7
11111
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 264 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 12716 KB Output is correct
2 Correct 175 ms 12684 KB Output is correct
3 Correct 187 ms 12736 KB Output is correct
4 Correct 222 ms 13120 KB Output is correct
5 Correct 233 ms 13388 KB Output is correct
6 Correct 215 ms 13104 KB Output is correct
7 Correct 264 ms 12980 KB Output is correct
8 Correct 262 ms 14424 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 264 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 166 ms 12716 KB Output is correct
9 Correct 175 ms 12684 KB Output is correct
10 Correct 187 ms 12736 KB Output is correct
11 Correct 222 ms 13120 KB Output is correct
12 Correct 233 ms 13388 KB Output is correct
13 Correct 215 ms 13104 KB Output is correct
14 Correct 264 ms 12980 KB Output is correct
15 Correct 262 ms 14424 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Halted 0 ms 0 KB -