oj.uz

Submission #828979

# Submission time Handle Problem Language Result Execution time Memory
828979 2023-08-17T22:22:52 Z arnold518 Radio Towers (IOI22_towers) C++17
17 / 100
 748 ms 18212 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);
	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

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 295 ms 9072 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 1 ms 384 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 1676 KB Output is correct
2 Correct 665 ms 5932 KB Output is correct
3 Correct 553 ms 5896 KB Output is correct
4 Correct 572 ms 5960 KB Output is correct
5 Correct 676 ms 5932 KB Output is correct
6 Correct 537 ms 5924 KB Output is correct
7 Correct 485 ms 5960 KB Output is correct
8 Correct 569 ms 18212 KB Output is correct
9 Correct 748 ms 5544 KB Output is correct
10 Correct 630 ms 13080 KB Output is correct
11 Correct 647 ms 5576 KB Output is correct
12 Correct 44 ms 5964 KB Output is correct
13 Correct 41 ms 5928 KB Output is correct
14 Correct 41 ms 5924 KB Output is correct
15 Correct 19 ms 5544 KB Output is correct
16 Correct 28 ms 16932 KB Output is correct
17 Correct 37 ms 5800 KB Output is correct
18 Correct 42 ms 5948 KB Output is correct
19 Correct 40 ms 5936 KB Output is correct
20 Correct 40 ms 5924 KB Output is correct
21 Correct 43 ms 5928 KB Output is correct
22 Correct 40 ms 5960 KB Output is correct
23 Correct 40 ms 5968 KB Output is correct
24 Correct 25 ms 18060 KB Output is correct
25 Correct 20 ms 5540 KB Output is correct
26 Correct 33 ms 13128 KB Output is correct
27 Correct 28 ms 5532 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 464 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 1 ms 336 KB Output is correct
38 Correct 1 ms 336 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 592 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 464 KB Output is correct
43 Correct 1 ms 336 KB Output is correct

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

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