Submission #410672

#	Time	Username	Problem	Language	Result	Execution time	Memory
410672		dynam1c	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5077 ms	524292 KiB

street_lamps

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q;
	cin >> n >> q;
	vector<string> arr(1);
	cin >> arr[0];
	for (int qq = 0; qq < q; qq++) {
		string t;
		cin >> t;
		if (t == "query") {
			int l, r;
			cin >> l >> r;
			l--, r--;
			int res = arr.size();
			for (string s : arr)
				for (int i = l; i < r; i++)
					if (s[i] == '0') {
						res--;
						break;
					}
			cout << res << endl;
		}
		arr.push_back(arr.back());
		if (t == "toggle") {
			int i;
			cin >> i;
			i--;
			arr.back()[i] = arr.back()[i] == '0' ? '1' : '0';
		}
	}
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20