Submission #828979

#	Time	Username	Problem	Language	Result	Execution time	Memory
828979		arnold518	Radio Towers (IOI22_towers)	C++17	17 / 100	748 ms	18212 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 1e9+7;

int N, A[MAXN+10];

struct SEG
{
	pii minv[MAXN*4+10], maxv[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			minv[node]={A[tl], tl};
			maxv[node]={A[tl], tl};
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		minv[node]=min(minv[node*2], minv[node*2+1]);
		maxv[node]=max(maxv[node*2], maxv[node*2+1]);
	}
	pii query1(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return minv[node];
		if(r<tl || tr<l) return {INF, 0};
		int mid=tl+tr>>1;
		return min(query1(node*2, tl, mid, l, r), query1(node*2+1, mid+1, tr, l, r));
	}
	pii query2(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return maxv[node];
		if(r<tl || tr<l) return {-INF, 0};
		int mid=tl+tr>>1;
		return max(query2(node*2, tl, mid, l, r), query2(node*2+1, mid+1, tr, l, r));
	}
}seg;

int cnt;
vector<int> V;

void solve(int l, int r)
{
	if(l>r) return;
	if(l==r) cnt++;
	pii p=seg.query2(1, 1, N, l, r);
	if(l!=p.second && p.second!=r) V.push_back(p.first-max(seg.query1(1, 1, N, l, p.second-1).first, seg.query1(1, 1, N, p.second+1, r).first));
	solve(l, p.second-1);
	solve(p.second+1, r);
}

void init(int _N, vector<int> _H)
{
	N=_N;
	for(int i=1; i<=N; i++) A[i]=_H[i-1];
	seg.init(1, 1, N);
	solve(1, N);
	sort(V.begin(), V.end());
}

int max_towers(int L, int R, int D) 
{
	L++; R++;
	return cnt-(lower_bound(V.begin(), V.end(), D)-V.begin());
}

Compilation message (stderr)

towers.cpp: In member function 'void SEG::init(int, int, int)':
towers.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int mid=tl+tr>>1;
      |           ~~^~~
towers.cpp: In member function 'pii SEG::query1(int, int, int, int, int)':
towers.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid=tl+tr>>1;
      |           ~~^~~
towers.cpp: In member function 'pii SEG::query2(int, int, int, int, int)':
towers.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=tl+tr>>1;
      |           ~~^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23