제출 #447834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447834		nonsensenonsense1	가로등 (APIO19_street_lamps)	C++17	100 / 100	3181 ms	125216 KiB

street_lamps

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>

const int N = 300000;
const int T = 1048575;
int n, q;
char s[N + 1], type[7];
std::map<std::pair<int, int>, int> mp;
std::pair<int, int> qry[N];
std::vector<int> all[T], bit[T];
bool read = false;

void tree_reserve(int lend, int rend, int v = 0, int tl = 0, int tr = n) 
{
	all[v].push_back(lend);
	if (tr - tl != 1) {
		int m = tl + tr >> 1;
		if (rend < m) tree_reserve(lend, rend, (v << 1) + 1, tl, m);
		else tree_reserve(lend, rend, (v << 1) + 2, m, tr);
	}
}

void bit_add(std::vector<int> &bit, int i, int d) 
{
	int size = (int)bit.size();
	while (i < size) {
		bit[i] += d;
		i |= i + 1;
	}
}

int bit_query(std::vector<int> &bit, int i) 
{
	int s = 0;
	while (i >= 0) {
		s += bit[i];
		i = (i & i + 1) - 1;
	}
	return s;
}

void tree_build(int v = 0, int tl = 0, int tr = n) 
{
	std::sort(all[v].begin(), all[v].end());
	all[v].resize(std::unique(all[v].begin(), all[v].end()) - all[v].begin());
	bit[v].resize(all[v].size());
	if (tr - tl != 1) {
		int m = tl + tr >> 1;
		tree_build((v << 1) + 1, tl, m);
		tree_build((v << 1) + 2, m, tr);
	}
}

void tree_add(int lend, int rend, int amt, int v = 0, int tl = 0, int tr = n) 
{
	bit_add(bit[v], std::lower_bound(all[v].begin(), all[v].end(), lend) - all[v].begin(), amt);
	if (tr - tl != 1) {
		int m = tl + tr >> 1;
		if (rend < m) tree_add(lend, rend, amt, (v << 1) + 1, tl, m);
		else tree_add(lend, rend, amt, (v << 1) + 2, m, tr);
	}
}

int tree_query(int l, int r, int lend, int v = 0, int tl = 0, int tr = n) 
{
	if (tl >= r || tr <= l) return 0;
	if (tl >= l && tr <= r) return bit_query(bit[v], std::upper_bound(all[v].begin(), all[v].end(), lend) - all[v].begin() - 1);
	int m = tl + tr >> 1;
	return tree_query(l, r, lend, (v << 1) + 1, tl, m) + tree_query(l, r, lend, (v << 1) + 2, m, tr);
}

void remove(std::pair<int, int> seg, int cur) 
{
	if (read) tree_add(seg.first, seg.second - 1, cur - mp[seg]);
	else tree_reserve(seg.first, seg.second - 1);
	mp.erase(seg);
}

void add(std::pair<int, int> seg, int cur) 
{
	if (seg.first < seg.second) mp.insert(std::make_pair(seg, cur));
}

void update(int p, int i) 
{
	std::map<std::pair<int, int>, int>::iterator next_it = mp.lower_bound(std::make_pair(p, ~(1 << 31)));
	if (next_it != mp.begin() && prev(next_it)->first.second > p) {
		std::pair<int, int> seg = prev(next_it)->first;
		remove(seg, i);
		add(std::make_pair(seg.first, p), i);
		add(std::make_pair(p + 1, seg.second), i);
	}
	else {
		bool p1 = next_it != mp.begin() && prev(next_it)->first.second == p, p2 = next_it != mp.end() && next_it->first.first == p + 1;
		if (p1) {
			if (p2) {
				std::pair<int, int> seg(prev(next_it)->first.first, next_it->first.second);
				remove(std::make_pair(seg.first, p), i);
				remove(std::make_pair(p + 1, seg.second), i);
				add(seg, i);
			}
			else {
				int left = prev(next_it)->first.first;
				remove(std::make_pair(left, p), i);
				add(std::make_pair(left, p + 1), i);
			}
		}
		else if (p2) {
			int right = next_it->first.second;
			remove(std::make_pair(p + 1, right), i);
			add(std::make_pair(p, right), i);
		}
		else add(std::make_pair(p, p + 1), i);
	}
}

void init() 
{
	for (int i = 0; i < n; ++i) if (s[i] == '1') {
		int j = i;
		for (++i; s[i] == '1'; ++i);
		add(std::make_pair(j, i), -1);
	}
}

int answer(int l, int r, int cur) 
{
	std::map<std::pair<int, int>, int>::iterator next_it = mp.lower_bound(std::make_pair(l, ~(1 << 31)));
	int now = 0;
	if (next_it != mp.begin() && prev(next_it)->first.second >= r) now = cur - prev(next_it)->second;
	return now + tree_query(r - 1, n, l);
}

int main() 
{
	scanf("%d%d%s", &n, &q, s);
	init();
	for (int i = 0; i < q; ++i) {
		scanf("%s", type);
		if (*type == 't') {
			int ind;
			scanf("%d", &qry[i].first);
			--qry[i].first;
			update(qry[i].first, i);
			qry[i].second = -1;
		}
		else {
			scanf("%d%d", &qry[i].first, &qry[i].second);
			--qry[i].first;
			--qry[i].second;
		}
	}
	read = true;
	tree_build();
	mp.clear();
	init();
	for (int i = 0; i < q; ++i) {
		if (qry[i].second == -1) update(qry[i].first, i);
		else printf("%d\n", answer(qry[i].first, qry[i].second, i));
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'void tree_reserve(int, int, int, int, int)':
street_lamps.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   int m = tl + tr >> 1;
      |           ~~~^~~~
street_lamps.cpp: In function 'int bit_query(std::vector<int>&, int)':
street_lamps.cpp:40:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   40 |   i = (i & i + 1) - 1;
      |            ~~^~~
street_lamps.cpp: In function 'void tree_build(int, int, int)':
street_lamps.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int m = tl + tr >> 1;
      |           ~~~^~~~
street_lamps.cpp: In function 'void tree_add(int, int, int, int, int, int)':
street_lamps.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |   int m = tl + tr >> 1;
      |           ~~~^~~~
street_lamps.cpp: In function 'int tree_query(int, int, int, int, int, int)':
street_lamps.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int m = tl + tr >> 1;
      |          ~~~^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:144:8: warning: unused variable 'ind' [-Wunused-variable]
  144 |    int ind;
      |        ^~~
street_lamps.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d%d%s", &n, &q, s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%s", type);
      |   ~~~~~^~~~~~~~~~~~
street_lamps.cpp:145:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |    scanf("%d", &qry[i].first);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |    scanf("%d%d", &qry[i].first, &qry[i].second);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20