oj.uz

Submission #733338

# Submission time Handle Problem Language Result Execution time Memory
733338 2023-04-30T13:53:01 Z minhcool Street Lamps (APIO19_street_lamps) C++17
40 / 100
 314 ms 16176 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 + 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 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 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 171 ms 14472 KB Output is correct
2 Correct 202 ms 14372 KB Output is correct
3 Correct 207 ms 14348 KB Output is correct
4 Correct 269 ms 14748 KB Output is correct
5 Correct 259 ms 15152 KB Output is correct
6 Correct 242 ms 14808 KB Output is correct
7 Correct 298 ms 14708 KB Output is correct
8 Correct 314 ms 16176 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 2 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 Incorrect 2 ms 596 KB Output isn't correct
2 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 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 171 ms 14472 KB Output is correct
9 Correct 202 ms 14372 KB Output is correct
10 Correct 207 ms 14348 KB Output is correct
11 Correct 269 ms 14748 KB Output is correct
12 Correct 259 ms 15152 KB Output is correct
13 Correct 242 ms 14808 KB Output is correct
14 Correct 298 ms 14708 KB Output is correct
15 Correct 314 ms 16176 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Incorrect 2 ms 468 KB Output isn't correct
18 Halted 0 ms 0 KB -