oj.uz

Submission #402031

# Submission time Handle Problem Language Result Execution time Memory
402031 2021-05-11T08:24:17 Z pavement Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 457196 KB 
#include <bits/stdc++.h>
using namespace std;

int N, Q, x, a, b, l, r;
bool A[300005];
char tmp;
string s;
set<pair<int, int> > S;
map<int, int> ft[300005];

inline int ls(int x) {
	return x & -x;
}

void upd(int l1, int l2, int r1, int r2, int v) {
	// add v to (l1, r1)
	for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] += v;
	
	// add -v to (l1, r2 + 1)
	for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r2 + 1; j <= N + 1; j += ls(j))
			ft[i][j] -= v;
	
	// add -v to (l2 + 1, r1)
	for (int i = l2 + 1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] -= v;
	
	// add v to (l2 + 1, r2 + 1)
	for (int i = l2 + 1; i <= N + 1; i += ls(i))
		for (int j = r2 + 1; j <= N + 1; j += ls(j))
			ft[i][j] += v;
}

int qry(int x, int y) {
	int r = 0;
	for (int i = x; i; i -= ls(i))
		for (int j = y; j; j -= ls(j))
			r += ft[i][j];
	return r;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		A[i] = tmp - '0';
		if (A[i]) {
			if (i == 1 || !A[i - 1]) S.emplace(i, i);
			else {
				int lft = S.rbegin()->first;
				S.erase(--S.end());
				S.emplace(lft, i);
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cin >> s;
		if (s == "toggle") {
			cin >> x;
			if (A[x]) {
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				assert(it != S.begin());
				--it;
				l = it->first;
				r = it->second + 1;
				
				// fix S
				S.erase(it);
				if (l < x) S.emplace(l, x - 1);
				if (x < r - 1) S.emplace(x + 1, r - 1);
				
				assert(l <= x && x + 1 <= r);
				// we know that [l, x] can currently reach [x + 1, r]
				upd(l, x, x + 1, r, i);
			} else {
				vector<set<pair<int, int> >::iterator> del;
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				if (it != S.end() && it->first == x + 1) r = it->second + 1, del.push_back(it);
				else r = x + 1;
				if (it != S.begin()) {
					--it;
					if (it->second == x - 1) l = it->first, del.push_back(it);
					else l = x;
				} else l = x;
				
				// fix S
				for (auto i : del) S.erase(i);
				S.emplace(l, r - 1);
				
				// we know that [l, x] cannot currently reach [x + 1, r]
				upd(l, x, x + 1, r, -i);
			}
			A[x] ^= 1;
		} else {
			cin >> a >> b;
			auto it = S.upper_bound(make_pair(a, (int)1e9));
			if (it != S.begin()) {
				--it;
				if (b <= it->second + 1) {
					cout << qry(a, b) + i << '\n';
					goto done;
				}
			}
			cout << qry(a, b) << '\n';
			done:;
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14284 KB Output is correct
2 Correct 10 ms 14388 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Correct 11 ms 14404 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14312 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 18504 KB Output is correct
2 Correct 806 ms 19088 KB Output is correct
3 Correct 2476 ms 25608 KB Output is correct
4 Execution timed out 5063 ms 263548 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14936 KB Output is correct
2 Correct 14 ms 15052 KB Output is correct
3 Correct 14 ms 15192 KB Output is correct
4 Correct 15 ms 15052 KB Output is correct
5 Execution timed out 5083 ms 239576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15052 KB Output is correct
2 Correct 13 ms 15056 KB Output is correct
3 Correct 13 ms 15052 KB Output is correct
4 Correct 14 ms 14796 KB Output is correct
5 Execution timed out 5079 ms 457196 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14284 KB Output is correct
2 Correct 10 ms 14388 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Correct 11 ms 14404 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 9 ms 14312 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 464 ms 18504 KB Output is correct
9 Correct 806 ms 19088 KB Output is correct
10 Correct 2476 ms 25608 KB Output is correct
11 Execution timed out 5063 ms 263548 KB Time limit exceeded
12 Halted 0 ms 0 KB -