oj.uz

Submission #630814

# Submission time Handle Problem Language Result Execution time Memory
630814 2022-08-17T07:02:19 Z prvocislo Radio Towers (IOI22_towers) C++17
0 / 100
 822 ms 36796 KB 
#include "towers.h"
#include <algorithm>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

const int maxn = 1 << 17;
struct node1
{
	int mi, mx, dix, dxi;
	node1() { mi = 1e9, mx = -1e9, dix = 0, dxi = 0; }
};
vector<node1> tmx(maxn * 2);
vector<int> h;
node1 merge(node1 l, node1 r)
{
	node1 n;
	n.mi = min(l.mi, r.mi);
	n.mx = max(l.mx, r.mx);
	n.dix = max({ l.dix, r.dix, r.mx - l.mi });
	n.dxi = max({ l.dxi, r.dxi, l.mx - r.mi });
	return n;
}
node1 query(int l, int r)
{
	node1 n;
	for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) n = merge(tmx[l++], n);
		if (r & 1) n = merge(n, tmx[--r]);
	}
	return n;
}
struct node2 { int tim, mi, mx; };
bool cmp(node2 a, node2 b) { return a.tim < b.tim; }
bool cmp2(node2 a, int t) { return a.tim < t; }
vector<vector<node2> > tr(maxn * 2);
void update(int i, int t, int x)
{
	for (i += maxn; i > 0; i >>= 1) tr[i].push_back({ t, x, x });
}
void upd(int vr, int t, int& mi, int& mx, int& cnt)
{
	int i = lower_bound(tr[vr].begin(), tr[vr].end(), t, cmp2) - tr[vr].begin();
	if (i == tr[vr].size()) return;
	mi = min(mi, tr[vr][i].mi), mx = max(mx, tr[vr][i].mx), cnt += tr[vr].size() - i;
}
void query(int l, int r, int t, int& mi, int& mx, int& cnt)
{
	for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) upd(l++, t, mi, mx, cnt);
		if (r & 1) upd(--r, t, mi, mx, cnt);
	}
}
void init(int n, vector<int> H) 
{
	h = H;
	for (int i = 0; i < n; i++) tmx[maxn + i].mi = tmx[maxn + i].mx = h[i];
	for (int i = maxn - 1; i > 0; i--) tmx[i] = merge(tmx[(i << 1)], tmx[(i << 1) | 1]);
	vector<int> l(n, -1), r(n, n);
	vector<int> st;
	for (int i = 0; i < n; i++)
	{
		while (!st.empty() && h[st.back()] > h[i]) st.pop_back();
		if (!st.empty()) l[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	for (int i = n - 1; i >= 0; i--)
	{
		while (!st.empty() && h[st.back()] > h[i]) st.pop_back();
		if (!st.empty()) r[i] = st.back();
		st.push_back(i);
	}
	for (int i = 0; i < n; i++)
	{
		int ml = query(l[i] + 1, i - 1).mx, mr = query(i + 1, r[i] - 1).mx;
		int t = max(0, min(ml - h[i], mr - h[i]));
		update(i, t, i);
	}
	for (int i = 0; i < maxn * 2; i++)
	{
		sort(tr[i].begin(), tr[i].end(), cmp);
		for (int j = (int)tr[i].size() - 2; j >= 0; j--) tr[i][j].mi = min(tr[i][j].mi, tr[i][j + 1].mi), tr[i][j].mx = max(tr[i][j].mx, tr[i][j + 1].mx);
	}
}
int max_towers(int l, int r, int d) 
{
	int mi = 1e9, mx = -1e9, cnt = 0;
	query(l, r, d, mi, mx, cnt);
	if (cnt == 0) return 1;
	int lo = l, hi = mi - 1;
	while (lo < hi)
	{
		int m = (lo + hi + 1) / 2;
		if (query(m, mi - 1).mx >= h[l] + d) lo = m;
		else hi = m - 1;
	}
	if (query(l, lo).dix >= d) cnt++;
	lo = mx + 1, hi = r;
	while (lo < hi)
	{
		int m = (lo + hi) / 2;
		if (query(mx + 1, m).mx >= h[l] + d) hi = m;
		else lo = m + 1;
	}
	if (query(lo, r).dxi >= d) cnt++;
	return cnt;
}

Compilation message

towers.cpp: In function 'void upd(int, int, int&, int&, int&)':
towers.cpp:46:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  if (i == tr[vr].size()) return;
      |      ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 372 ms 26396 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10576 KB Output is correct
2 Correct 9 ms 10996 KB Output is correct
3 Correct 8 ms 11088 KB Output is correct
4 Correct 9 ms 11108 KB Output is correct
5 Correct 10 ms 11088 KB Output is correct
6 Correct 10 ms 11060 KB Output is correct
7 Incorrect 9 ms 11108 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10576 KB Output is correct
2 Correct 9 ms 10996 KB Output is correct
3 Correct 8 ms 11088 KB Output is correct
4 Correct 9 ms 11108 KB Output is correct
5 Correct 10 ms 11088 KB Output is correct
6 Correct 10 ms 11060 KB Output is correct
7 Incorrect 9 ms 11108 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 822 ms 36796 KB 14th lines differ - on the 1st token, expected: '16602', found: '16601'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 370 ms 16752 KB 3rd lines differ - on the 1st token, expected: '150', found: '149'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10576 KB Output is correct
2 Correct 9 ms 10996 KB Output is correct
3 Correct 8 ms 11088 KB Output is correct
4 Correct 9 ms 11108 KB Output is correct
5 Correct 10 ms 11088 KB Output is correct
6 Correct 10 ms 11060 KB Output is correct
7 Incorrect 9 ms 11108 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 372 ms 26396 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -