oj.uz

답안 #197947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197947 2020-01-24T11:56:07 Z QCFium 가로등 (APIO19_street_lamps) C++14
20 / 100
 5000 ms 163728 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 (r > node->key) return node->val + node->l->sum + (node->r == NONE ? 0 : sum(node->r, r));
		else return node->l == NONE ? 0 : sum(node->l, r);
	}
	void add(int index, int val) { root = add(root, index, val); }
	int sum(int r) { return root == NONE ? 0 : 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_) {
		for (n = 1; n < h_; n <<= 1);
		data.resize(n * 2);
	}
	void add(int i, int j, int val) {
		for (i += n; i; i >>= 1) data[i].add(j, val);
	}
	int sum(int x, int y) {
		int l = 0, r = x;
		int res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) res += data[--r].sum(y);
			if (l & 1) res += data[l++].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

# 결과 실행 시간 메모리 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 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 915 ms 1520 KB Output is correct
2 Correct 1074 ms 1756 KB Output is correct
3 Correct 1891 ms 6996 KB Output is correct
4 Execution timed out 5069 ms 141480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Execution timed out 5072 ms 156868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 2491 ms 84040 KB Output is correct
6 Correct 3711 ms 120696 KB Output is correct
7 Correct 4949 ms 153876 KB Output is correct
8 Execution timed out 5045 ms 163728 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 915 ms 1520 KB Output is correct
9 Correct 1074 ms 1756 KB Output is correct
10 Correct 1891 ms 6996 KB Output is correct
11 Execution timed out 5069 ms 141480 KB Time limit exceeded
12 Halted 0 ms 0 KB -