oj.uz

Submission #447834

# Submission time Handle Problem Language Result Execution time Memory
447834 2021-07-27T16:35:45 Z nonsensenonsense1 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3181 ms 125216 KB 
#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;
}

Compilation message

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49444 KB Output is correct
2 Correct 28 ms 49476 KB Output is correct
3 Correct 27 ms 49528 KB Output is correct
4 Correct 26 ms 49496 KB Output is correct
5 Correct 27 ms 49500 KB Output is correct
6 Correct 28 ms 49500 KB Output is correct
7 Correct 27 ms 49436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 62228 KB Output is correct
2 Correct 406 ms 63648 KB Output is correct
3 Correct 691 ms 68748 KB Output is correct
4 Correct 1893 ms 100828 KB Output is correct
5 Correct 2125 ms 104056 KB Output is correct
6 Correct 2068 ms 104444 KB Output is correct
7 Correct 255 ms 58708 KB Output is correct
8 Correct 278 ms 60140 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49588 KB Output is correct
2 Correct 29 ms 49660 KB Output is correct
3 Correct 29 ms 49628 KB Output is correct
4 Correct 27 ms 49464 KB Output is correct
5 Correct 2866 ms 125216 KB Output is correct
6 Correct 2760 ms 121524 KB Output is correct
7 Correct 2119 ms 103412 KB Output is correct
8 Correct 272 ms 59972 KB Output is correct
9 Correct 145 ms 55092 KB Output is correct
10 Correct 172 ms 55544 KB Output is correct
11 Correct 155 ms 55752 KB Output is correct
12 Correct 260 ms 58668 KB Output is correct
13 Correct 251 ms 60080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49484 KB Output is correct
2 Correct 29 ms 49624 KB Output is correct
3 Correct 40 ms 49576 KB Output is correct
4 Correct 30 ms 49604 KB Output is correct
5 Correct 459 ms 64900 KB Output is correct
6 Correct 1220 ms 88544 KB Output is correct
7 Correct 2048 ms 103904 KB Output is correct
8 Correct 3181 ms 123052 KB Output is correct
9 Correct 495 ms 66276 KB Output is correct
10 Correct 457 ms 66724 KB Output is correct
11 Correct 490 ms 66220 KB Output is correct
12 Correct 431 ms 66820 KB Output is correct
13 Correct 486 ms 66096 KB Output is correct
14 Correct 438 ms 67108 KB Output is correct
15 Correct 247 ms 58688 KB Output is correct
16 Correct 250 ms 59984 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49444 KB Output is correct
2 Correct 28 ms 49476 KB Output is correct
3 Correct 27 ms 49528 KB Output is correct
4 Correct 26 ms 49496 KB Output is correct
5 Correct 27 ms 49500 KB Output is correct
6 Correct 28 ms 49500 KB Output is correct
7 Correct 27 ms 49436 KB Output is correct
8 Correct 341 ms 62228 KB Output is correct
9 Correct 406 ms 63648 KB Output is correct
10 Correct 691 ms 68748 KB Output is correct
11 Correct 1893 ms 100828 KB Output is correct
12 Correct 2125 ms 104056 KB Output is correct
13 Correct 2068 ms 104444 KB Output is correct
14 Correct 255 ms 58708 KB Output is correct
15 Correct 278 ms 60140 KB Output is correct
16 Correct 30 ms 49588 KB Output is correct
17 Correct 29 ms 49660 KB Output is correct
18 Correct 29 ms 49628 KB Output is correct
19 Correct 27 ms 49464 KB Output is correct
20 Correct 2866 ms 125216 KB Output is correct
21 Correct 2760 ms 121524 KB Output is correct
22 Correct 2119 ms 103412 KB Output is correct
23 Correct 272 ms 59972 KB Output is correct
24 Correct 145 ms 55092 KB Output is correct
25 Correct 172 ms 55544 KB Output is correct
26 Correct 155 ms 55752 KB Output is correct
27 Correct 260 ms 58668 KB Output is correct
28 Correct 251 ms 60080 KB Output is correct
29 Correct 33 ms 49484 KB Output is correct
30 Correct 29 ms 49624 KB Output is correct
31 Correct 40 ms 49576 KB Output is correct
32 Correct 30 ms 49604 KB Output is correct
33 Correct 459 ms 64900 KB Output is correct
34 Correct 1220 ms 88544 KB Output is correct
35 Correct 2048 ms 103904 KB Output is correct
36 Correct 3181 ms 123052 KB Output is correct
37 Correct 495 ms 66276 KB Output is correct
38 Correct 457 ms 66724 KB Output is correct
39 Correct 490 ms 66220 KB Output is correct
40 Correct 431 ms 66820 KB Output is correct
41 Correct 486 ms 66096 KB Output is correct
42 Correct 438 ms 67108 KB Output is correct
43 Correct 247 ms 58688 KB Output is correct
44 Correct 250 ms 59984 KB Output is correct
45 Correct 145 ms 55720 KB Output is correct
46 Correct 229 ms 57312 KB Output is correct
47 Correct 930 ms 74552 KB Output is correct
48 Correct 1842 ms 100432 KB Output is correct
49 Correct 165 ms 56132 KB Output is correct
50 Correct 163 ms 55936 KB Output is correct
51 Correct 169 ms 56100 KB Output is correct
52 Correct 172 ms 56428 KB Output is correct
53 Correct 170 ms 56388 KB Output is correct
54 Correct 173 ms 56356 KB Output is correct