oj.uz

답안 #402033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402033 2021-05-11T08:25:54 Z pavement 가로등 (APIO19_street_lamps) C++17
40 / 100
 5000 ms 524292 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

int N, Q, x, a, b, l, r;
bool A[300005];
char tmp;
string s;
set<pair<int, int> > S;
gp_hash_table<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

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 63668 KB Output is correct
2 Correct 67 ms 63720 KB Output is correct
3 Correct 64 ms 63604 KB Output is correct
4 Correct 65 ms 63716 KB Output is correct
5 Correct 64 ms 63684 KB Output is correct
6 Correct 68 ms 63728 KB Output is correct
7 Correct 68 ms 63724 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 64624 KB Output is correct
2 Correct 383 ms 64812 KB Output is correct
3 Correct 765 ms 70032 KB Output is correct
4 Correct 3485 ms 306872 KB Output is correct
5 Correct 3304 ms 312404 KB Output is correct
6 Correct 3467 ms 318016 KB Output is correct
7 Correct 1580 ms 185660 KB Output is correct
8 Correct 1623 ms 187120 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 64068 KB Output is correct
2 Correct 72 ms 64112 KB Output is correct
3 Correct 71 ms 64244 KB Output is correct
4 Correct 70 ms 64128 KB Output is correct
5 Correct 4747 ms 305916 KB Output is correct
6 Execution timed out 5100 ms 384908 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 64308 KB Output is correct
2 Correct 71 ms 64204 KB Output is correct
3 Correct 71 ms 64172 KB Output is correct
4 Correct 72 ms 63992 KB Output is correct
5 Runtime error 3294 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 63668 KB Output is correct
2 Correct 67 ms 63720 KB Output is correct
3 Correct 64 ms 63604 KB Output is correct
4 Correct 65 ms 63716 KB Output is correct
5 Correct 64 ms 63684 KB Output is correct
6 Correct 68 ms 63728 KB Output is correct
7 Correct 68 ms 63724 KB Output is correct
8 Correct 298 ms 64624 KB Output is correct
9 Correct 383 ms 64812 KB Output is correct
10 Correct 765 ms 70032 KB Output is correct
11 Correct 3485 ms 306872 KB Output is correct
12 Correct 3304 ms 312404 KB Output is correct
13 Correct 3467 ms 318016 KB Output is correct
14 Correct 1580 ms 185660 KB Output is correct
15 Correct 1623 ms 187120 KB Output is correct
16 Correct 73 ms 64068 KB Output is correct
17 Correct 72 ms 64112 KB Output is correct
18 Correct 71 ms 64244 KB Output is correct
19 Correct 70 ms 64128 KB Output is correct
20 Correct 4747 ms 305916 KB Output is correct
21 Execution timed out 5100 ms 384908 KB Time limit exceeded
22 Halted 0 ms 0 KB -