oj.uz

Submission #197950

# Submission time Handle Problem Language Result Execution time Memory
197950 2020-01-24T12:00:31 Z QCFium Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3555 ms 90732 KB 
#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int64_t rs64() {
	long long n;
	scanf("%lld", &n);
	return n;
}

struct AVL {
	struct Node {
		Node *l;
		Node *r;
		int key;
		int val;
		int sum;
		int size;
		int height;
		Node *fetch() {
			size = 1 + l->size + r->size;
			height = 1 + std::max(l->height, r->height);
			sum = val + l->sum + r->sum;
			return this;
		}
		Node *rotate_l() {
			Node *new_root = r;
			r = new_root->l;
			new_root->l = this;
			return fetch(), new_root->fetch();
		}
		Node *rotate_r() {
			Node *new_root = l;
			l = new_root->r;
			new_root->r = this;
			return fetch(), new_root->fetch();
		}
		int height_diff() { return l->height - r->height; }
		Node *balance() {
			int dif = height_diff();
			if (dif == 2) {
				if (l->height_diff() < 0) l = l->rotate_l();
				return rotate_r();
			} else if (dif == -2) {
				if (r->height_diff() > 0) r = r->rotate_r();
				return rotate_l();
			} else return fetch();
		}
	};
	static Node *nodes, *NONE;
	static int head;
	Node *root = NONE;
	AVL() {
		if (!head) nodes[head++] = {NONE, NONE, 0, 0, 0, 0, 0};
	}
	Node *add(Node *node, int index, int val) {
		if (node == NONE) return &(nodes[head++] = {NONE, NONE, index, val, val, 1, 1});
		if (index < node->key) node->l = add(node->l, index, val);
		else if (index > node->key) node->r = add(node->r, index, val);
		else node->val += val;
		return node->balance();
	}
	int sum(Node *node, int r) {
		if (node == NONE) return 0;
		if (r > node->key) return node->val + node->l->sum + sum(node->r, r);
		else return sum(node->l, r);
	}
	void add(int index, int val) { root = add(root, index, val); }
	int sum(int r) { return sum(root, r); }
};
AVL::Node *AVL::nodes = (Node *) malloc(sizeof(Node) * 10000000), *AVL::NONE = nodes;
int AVL::head = 0;

struct SegTree2D {
	std::vector<AVL> data;
	int n;
	SegTree2D (int h_, int w_) : n(h_) {
		data.resize(h_ + 1);
	}
	void add(int i, int j, int val) {
		for (i++; i <= n; i += i & -i) data[i].add(j, val);
	}
	int sum(int x, int y) {
		int res = 0;
		for (; x; x -= x & -x) res += data[x].sum(y);
		return res;
	}
};

int main() {
	int n = ri(), q = ri();
	std::vector<bool> state(n);
	{
		std::string s;
		std::cin >> s;
		for (int i = 0; i < n; i++) state[i] = s[i] == '1';
	}
	std::set<std::pair<int, int> > range;
	
	SegTree2D tree(n + 1, n + 1);
	auto add = [&] (int l, int r, int val) {
		tree.add(l, 0, val);
		if (r < n) tree.add(l, r + 1, -val);
	};
	int time = 0;
	auto toggle = [&] (int i) {
		if (state[i]) {
			auto itr = std::prev(range.upper_bound({i, 1000000000}));
			if (itr->first < i) add(itr->first, i, q - time), range.insert({itr->first, i});
			if (i + 1 < itr->second) add(i + 1, itr->second, q - time), range.insert({i + 1, itr->second});
			add(itr->first, itr->second, time - q);
			range.erase(itr);
		} else {
			auto itr = range.lower_bound({i, 0});
			int l = i, r = i + 1;
			if (itr != range.end() && itr->first == r) r = itr->second, add(itr->first, itr->second, time - q), range.erase(itr++);
			if (itr != range.begin() && (--itr)->second == l) l = itr->first, add(itr->first, itr->second, time - q), range.erase(itr);
			add(l, r, q - time);
			range.insert({l, r});
		}
		state[i] = !state[i];
	};
	for (int i = 0; i < n; ) {
		for (; i < n && !state[i]; i++);
		if (i == n) break;
		int old_i = i;
		for (; i < n && state[i]; i++);
		range.insert({old_i, i});
		add(old_i, i, q);
	}
	
	
	for (int i = 0; i < q; i++) {
		time++;
		std::string type;
		std::cin >> type;
		if (type == "toggle") {
			int i = ri() - 1;
			toggle(i);
		} else if (type == "query") {
			int l = ri() - 1;
			int r = ri() - 1;
			int sum = tree.sum(l + 1, r + 1);
			auto itr = range.upper_bound({l, 1000000000});
			if (itr != range.begin() && std::prev(itr)->first <= l && std::prev(itr)->second >= r) sum -= q - i - 1;
			std::cout << sum << std::endl;
		}
	}
	
	
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int ri()':
street_lamps.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'int64_t rs64()':
street_lamps.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 4700 KB Output is correct
2 Correct 891 ms 5212 KB Output is correct
3 Correct 1289 ms 8080 KB Output is correct
4 Correct 3288 ms 75376 KB Output is correct
5 Correct 3068 ms 60056 KB Output is correct
6 Correct 3125 ms 79492 KB Output is correct
7 Correct 1129 ms 9524 KB Output is correct
8 Correct 1126 ms 10940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 3404 ms 87292 KB Output is correct
6 Correct 3526 ms 81748 KB Output is correct
7 Correct 2967 ms 63204 KB Output is correct
8 Correct 1145 ms 10996 KB Output is correct
9 Correct 850 ms 4292 KB Output is correct
10 Correct 930 ms 4472 KB Output is correct
11 Correct 921 ms 4748 KB Output is correct
12 Correct 1128 ms 9644 KB Output is correct
13 Correct 1130 ms 10796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 424 KB Output is correct
4 Correct 5 ms 508 KB Output is correct
5 Correct 2242 ms 43128 KB Output is correct
6 Correct 2667 ms 61016 KB Output is correct
7 Correct 3034 ms 79276 KB Output is correct
8 Correct 3555 ms 90732 KB Output is correct
9 Correct 725 ms 4336 KB Output is correct
10 Correct 463 ms 3448 KB Output is correct
11 Correct 725 ms 4344 KB Output is correct
12 Correct 462 ms 3320 KB Output is correct
13 Correct 729 ms 4216 KB Output is correct
14 Correct 469 ms 3324 KB Output is correct
15 Correct 1146 ms 9440 KB Output is correct
16 Correct 1134 ms 10940 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 802 ms 4700 KB Output is correct
9 Correct 891 ms 5212 KB Output is correct
10 Correct 1289 ms 8080 KB Output is correct
11 Correct 3288 ms 75376 KB Output is correct
12 Correct 3068 ms 60056 KB Output is correct
13 Correct 3125 ms 79492 KB Output is correct
14 Correct 1129 ms 9524 KB Output is correct
15 Correct 1126 ms 10940 KB Output is correct
16 Correct 4 ms 504 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 3404 ms 87292 KB Output is correct
21 Correct 3526 ms 81748 KB Output is correct
22 Correct 2967 ms 63204 KB Output is correct
23 Correct 1145 ms 10996 KB Output is correct
24 Correct 850 ms 4292 KB Output is correct
25 Correct 930 ms 4472 KB Output is correct
26 Correct 921 ms 4748 KB Output is correct
27 Correct 1128 ms 9644 KB Output is correct
28 Correct 1130 ms 10796 KB Output is correct
29 Correct 6 ms 376 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 5 ms 424 KB Output is correct
32 Correct 5 ms 508 KB Output is correct
33 Correct 2242 ms 43128 KB Output is correct
34 Correct 2667 ms 61016 KB Output is correct
35 Correct 3034 ms 79276 KB Output is correct
36 Correct 3555 ms 90732 KB Output is correct
37 Correct 725 ms 4336 KB Output is correct
38 Correct 463 ms 3448 KB Output is correct
39 Correct 725 ms 4344 KB Output is correct
40 Correct 462 ms 3320 KB Output is correct
41 Correct 729 ms 4216 KB Output is correct
42 Correct 469 ms 3324 KB Output is correct
43 Correct 1146 ms 9440 KB Output is correct
44 Correct 1134 ms 10940 KB Output is correct
45 Correct 473 ms 2852 KB Output is correct
46 Correct 537 ms 3072 KB Output is correct
47 Correct 1532 ms 31208 KB Output is correct
48 Correct 3100 ms 75024 KB Output is correct
49 Correct 1050 ms 4488 KB Output is correct
50 Correct 1052 ms 4600 KB Output is correct
51 Correct 1047 ms 4668 KB Output is correct
52 Correct 1063 ms 5240 KB Output is correct
53 Correct 1053 ms 5020 KB Output is correct
54 Correct 1055 ms 5172 KB Output is correct