oj.uz

Submission #410672

# Submission time Handle Problem Language Result Execution time Memory
410672 2021-05-23T10:09:55 Z dynam1c Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 524292 KB 
//#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.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5077 ms 3816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 15 ms 1264 KB Output is correct
3 Correct 28 ms 1232 KB Output is correct
4 Correct 133 ms 1340 KB Output is correct
5 Runtime error 695 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1248 KB Output is correct
2 Correct 41 ms 1280 KB Output is correct
3 Correct 28 ms 1384 KB Output is correct
4 Correct 3 ms 1356 KB Output is correct
5 Runtime error 231 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Execution timed out 5077 ms 3816 KB Time limit exceeded
9 Halted 0 ms 0 KB -