oj.uz

Submission #627638

# Submission time Handle Problem Language Result Execution time Memory
627638 2022-08-12T17:51:56 Z Noam527 Radio Towers (IOI22_towers) C++17
18 / 100
 1706 ms 76488 KB 
#include "towers.h"
#include <bits/stdc++.h>
const int OO = 0;
using namespace std;

struct info {
	int len[2][2];
	info(int x = -1) {
		len[0][0] = len[1][1] = -1e9;
		len[0][1] = len[1][0] = -1e9;
		if (x == 0) {
			len[0][0] = 1;
		}
		if (x == 1) {
			len[1][1] = 1;
		}
	}
	info operator * (const info &a) const {
		info res;
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
			res.len[i][j] = max(max(res.len[i][j], len[i][j]), a.len[i][j]);
		}
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
			res.len[i][k] = max(res.len[i][k], len[i][j] + a.len[1 ^ j][k]);
		}
		return res;
	}
	void print() {
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
			cout << i << " -> " << j << ": " << len[i][j] << '\n';
		}
	}
};
struct node {
	vector<pair<int, info>> data;
	node() {
		data.emplace_back(0, info());
	}
	void add(int tim, info i) {
		data.emplace_back(tim, i);
	}
	info& get(int tim) {
		tim = max(tim, 0);
		int lo = 0, hi = (int)data.size() - 1, mid;
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (data[mid].first <= tim) lo = mid;
			else hi = mid - 1;
		}
		return data[lo].second;
	}
};

struct segtree {
	int n;
	int tim;
	vector<node> t;
	segtree() {}
	segtree(int sz) {
		tim = 0;
		n = max(2, sz);
		while (n != (n & -n)) n += (n & -n);
		t.resize(2 * n, node());
	}
	void fix(int x) {
		t[x].add(tim, t[2 * x + 1].get(tim) * t[2 * x + 2].get(tim));
	}
	void upd(int x, int val) {
		tim++;
		x += n - 1;
		t[x].add(tim, info(val));
		while (x) {
			x = (x - 1) / 2;
			fix(x);
		}
	}
	info query(int l, int r, int T) {
		if (l > r) return info();
		return query(l, r, T, 0, 0, n - 1);
	}
	info query(int l, int r, int T, int node, int nl, int nr) {
		if (nr < l || r < nl) return info();
		if (l <= nl && nr <= r) return t[node].get(T);
		int mid = (nl + nr) / 2;
		return query(l, r, T, 2 * node + 1, nl, mid) * query(l, r, T, 2 * node + 2, mid + 1, nr);
	}
};

int oldn;
vector<int> oldh;

int n;
vector<int> taken_ind;
vector<int> h;
vector<pair<int, int>> w;

segtree T;

void init(int N, std::vector<int> H) {
	oldn = N;
	oldh = H;
	h = { H[0], H[1] };
	taken_ind = { 0, 1 };
	for (int i = 2; i < oldn; i++) {
		if (abs(h[h.size() - 2] - h.back()) + abs(h.back() - H[i]) == abs(h[h.size() - 2] - H[i]))
			h.pop_back(), taken_ind.pop_back();
		h.push_back(H[i]);
		taken_ind.push_back(i);
	}
	n = h.size();
	
	for (int i = 0; i + 1 < h.size(); i++)
		w.emplace_back(abs(h[i] - h[i + 1]), i);
	if (OO) {
		cout << "w:\n";
		for (const auto &i : w) cout << i.first << " " << i.second << '\n';
	}
	sort(w.rbegin(), w.rend());
	
	T = segtree(n);
	for (auto &i : w) {
		if (h[i.second] < h[i.second + 1])
			T.upd(i.second, 0);
		else
			T.upd(i.second, 1);
	}
}

int bruteforce(int l, int r, int d) {
	int len = r - l + 1;
	int best = 0;
	for (int mask = 0; mask < (1 << len); mask++) {
		vector<int> val;
		for (int i = l; i <= r; i++) {
			if (mask & (1 << (i - l)))
				val.push_back(oldh[i]);
		}
		if (val.size() % 2 == 0) continue;
		bool good = true;
		for (int i = 0; i + 1 < val.size(); i++) {
			if (i % 2 == 0 && val[i] + d > val[i + 1]) good = false;
			if (i % 2 == 1 && val[i] - d < val[i + 1]) good = false;
		}
		if (good)
			best = max(best, (int)val.size() / 2 + 1);
	}
	return best;
}

int max_towers(int L, int R, int D) {
	// find time
	int lo = -1, hi = (int)w.size() - 1, mid;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		if (w[mid].first >= D) lo = mid;
		else hi = mid - 1;
	}
	int tim = lo + 1;

	// fix L, R
	auto it = lower_bound(taken_ind.begin(), taken_ind.end(), L);
	int LL = *it;
	int l = it - taken_ind.begin();
	it = prev(upper_bound(taken_ind.begin(), taken_ind.end(), R));
	int RR = *it;
	int r = it - taken_ind.begin();

	// break into cases - and also don't forget to consider the boundaries
	if (R < LL) {
		// nothing in between - this is a monotonic range
		return 1;
	}
	// there's something in between: l <= r
	if (OO) {
		cout << "data until now:\n";
		cout << "taken_ind: ";
		for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
		cout << "l LL " << l << " " << LL << '\n';
		cout << "r RR " << r << " " << RR << '\n';
		cout << "tim " << tim << '\n';
	}
	info q = T.query(l, r - 1, tim);
	if (OO) {
		cout << "from query received:\n";
		q.print();
	}
	if (L < LL) {
		// consider left boundary
		info boundary = info();
		if (oldh[L] + D <= oldh[LL])
			boundary = info(0);
		else if (oldh[L] - D >= oldh[LL])
			boundary = info(1);
		q = boundary * q;
	}
	if (RR < R) {
		// consider right boundary
		info boundary = info();
		if (oldh[RR] + D <= oldh[R])
			boundary = info(0);
		else if (oldh[RR] - D >= oldh[R])
			boundary = info(1);
		q = q * boundary;
	}
	return max(1, max(q.len[0][0], q.len[0][1]) / 2 + 1);
}

Compilation message

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i = 0; i + 1 < h.size(); i++)
      |                  ~~~~~~^~~~~~~~~~
towers.cpp: In function 'int bruteforce(int, int, int)':
towers.cpp:140:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   for (int i = 0; i + 1 < val.size(); i++) {
      |                   ~~~~~~^~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:177:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  177 |   for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
      |   ^~~
towers.cpp:177:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  177 |   for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
      |                                                     ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 976 KB Output is correct
2 Correct 794 ms 1440 KB Output is correct
3 Correct 779 ms 1352 KB Output is correct
4 Correct 793 ms 1436 KB Output is correct
5 Correct 1101 ms 1460 KB Output is correct
6 Correct 745 ms 1432 KB Output is correct
7 Correct 818 ms 1488 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 3 ms 1104 KB Output is correct
3 Incorrect 3 ms 1104 KB 1st lines differ - on the 1st token, expected: '91', found: '56'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 3 ms 1104 KB Output is correct
3 Incorrect 3 ms 1104 KB 1st lines differ - on the 1st token, expected: '91', found: '56'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 56636 KB Output is correct
2 Correct 1223 ms 56984 KB Output is correct
3 Correct 1340 ms 57168 KB Output is correct
4 Correct 1645 ms 75576 KB Output is correct
5 Correct 1360 ms 76308 KB Output is correct
6 Correct 1657 ms 75708 KB Output is correct
7 Correct 1706 ms 76408 KB Output is correct
8 Correct 599 ms 1444 KB Output is correct
9 Correct 753 ms 1448 KB Output is correct
10 Correct 727 ms 1516 KB Output is correct
11 Correct 773 ms 1420 KB Output is correct
12 Correct 916 ms 1444 KB Output is correct
13 Correct 723 ms 1436 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 232 ms 56828 KB Output is correct
18 Correct 358 ms 75820 KB Output is correct
19 Correct 371 ms 76488 KB Output is correct
20 Correct 12 ms 1360 KB Output is correct
21 Correct 12 ms 1360 KB Output is correct
22 Correct 224 ms 56784 KB Output is correct
23 Correct 387 ms 75912 KB Output is correct
24 Correct 397 ms 76400 KB Output is correct
25 Correct 10 ms 1444 KB Output is correct
26 Correct 11 ms 1436 KB Output is correct
27 Correct 2 ms 1104 KB Output is correct
28 Correct 3 ms 1360 KB Output is correct
29 Correct 3 ms 1360 KB Output is correct
30 Correct 1 ms 208 KB Output is correct
31 Correct 1 ms 224 KB Output is correct
32 Correct 2 ms 1104 KB Output is correct
33 Correct 3 ms 1360 KB Output is correct
34 Correct 3 ms 1360 KB Output is correct
35 Correct 0 ms 208 KB Output is correct
36 Correct 1 ms 208 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 10624 KB 1st lines differ - on the 1st token, expected: '7197', found: '7192'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 3 ms 1104 KB Output is correct
3 Incorrect 3 ms 1104 KB 1st lines differ - on the 1st token, expected: '91', found: '56'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 976 KB Output is correct
2 Correct 794 ms 1440 KB Output is correct
3 Correct 779 ms 1352 KB Output is correct
4 Correct 793 ms 1436 KB Output is correct
5 Correct 1101 ms 1460 KB Output is correct
6 Correct 745 ms 1432 KB Output is correct
7 Correct 818 ms 1488 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 3 ms 1104 KB Output is correct
13 Incorrect 3 ms 1104 KB 1st lines differ - on the 1st token, expected: '91', found: '56'
14 Halted 0 ms 0 KB -