oj.uz

Submission #828974

# Submission time Handle Problem Language Result Execution time Memory
828974 2023-08-17T21:51:05 Z arnold518 Radio Towers (IOI22_towers) C++17
0 / 100
 477 ms 9168 KB 
#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);
	pii q=seg.query1(1, 1, N, l, r);
	if(l!=p.second && p.second!=r) V.push_back(p.first-q.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

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

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '139'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '139'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 ms 5936 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '139'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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