oj.uz

Submission #410674

# Submission time Handle Problem Language Result Execution time Memory
410674 2021-05-23T10:20:22 Z dynam1c Street Lamps (APIO19_street_lamps) C++17
20 / 100
 204 ms 15492 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;
	string s;
	cin >> s;
	vector<int> accs(n), last(n);
	vector<vector<int>> upds(n);
	for (int qq = 0; qq < q; qq++) {
		string t;
		cin >> t;
		if (t == "query") {
			int i, r;
			cin >> i >> r;
			i--;
			for (int t : upds[i]) {
				if (s[i] == '1') accs[i] += t-last[i];
				last[i] = t;
				s[i] = s[i] == '1' ? '0' : '1';
			}
			upds[i].clear();
			cout << accs[i] + (s[i] == '1' ? qq+1-last[i] : 0) << endl;
		}
		if (t == "toggle") {
			int i;
			cin >> i;
			i--;
			upds[i].push_back(qq+1);
		}
	}
}
/* --- 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
0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1716 KB Output is correct
2 Correct 120 ms 1860 KB Output is correct
3 Correct 105 ms 2140 KB Output is correct
4 Correct 160 ms 14916 KB Output is correct
5 Correct 167 ms 15300 KB Output is correct
6 Correct 156 ms 15492 KB Output is correct
7 Correct 204 ms 11292 KB Output is correct
8 Correct 180 ms 12648 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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