oj.uz

Submission #733229

# Submission time Handle Problem Language Result Execution time Memory
733229 2023-04-30T09:30:35 Z minhcool Street Lamps (APIO19_street_lamps) C++17
40 / 100
 311 ms 14684 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] == '0') upd(j, 1);
			for(auto it : ques[i]){
				int mid = (it.fi.fi + it.fi.se) / 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}, it.se});
					else ques[i + 1].pb({{mid + 1, 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 13052 KB Output is correct
2 Correct 205 ms 12976 KB Output is correct
3 Correct 250 ms 13020 KB Output is correct
4 Correct 246 ms 13356 KB Output is correct
5 Correct 266 ms 13652 KB Output is correct
6 Correct 217 ms 13284 KB Output is correct
7 Correct 304 ms 13376 KB Output is correct
8 Correct 311 ms 14684 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 164 ms 13052 KB Output is correct
9 Correct 205 ms 12976 KB Output is correct
10 Correct 250 ms 13020 KB Output is correct
11 Correct 246 ms 13356 KB Output is correct
12 Correct 266 ms 13652 KB Output is correct
13 Correct 217 ms 13284 KB Output is correct
14 Correct 304 ms 13376 KB Output is correct
15 Correct 311 ms 14684 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -