Submission #197935

#	Time	Username	Problem	Language	Result	Execution time	Memory
197935		QCFium	가로등 (APIO19_street_lamps)	C++14	0 / 100	468 ms	524292 KiB

street_lamps

#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 SegTree {
	std::vector<std::vector<int> > data;
	SegTree (int h_, int w_) {
		data.resize(h_, std::vector<int> (w_, 0));
	}
	void add(int i, int j, int val) {
		data[i][j] += val;
	}
	int sum(int x1, int x2, int y1, int y2) {
		int res = 0;
		for (int i = x1; i < x2; i++) for (int j = y1; j < y2; j++) res += data[i][j];
		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;
	
	SegTree 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(0, l + 1, 0, 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 (stderr)

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: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20