oj.uz

Submission #692982

# Submission time Handle Problem Language Result Execution time Memory
692982 2023-02-02T08:19:28 Z Pyqe Radio Towers (IOI22_towers) C++17
17 / 100
 1036 ms 10700 KB 
#include <bits/stdc++.h>
#include "towers.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long nn=0,a[100069],ex[100069],zs=0;
multiset<long long> ms;
priority_queue<pair<long long,pair<long long,long long>>> pq;
bitset<100069> vtd;
pair<long long,long long> sq[100069];

void init(int n,vector<int> aa)
{
	long long i,k,l,w,e=0;
	multiset<long long>::iterator it;
	
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
	}
	a[0]=inf;
	a[n+1]=inf;
	for(i=1;i<=n;i++)
	{
		if(a[i]<a[i-1]&&a[i]<a[i+1])
		{
			if(!e)
			{
				nn++;
				ex[nn]=i;
				e=1;
			}
		}
		else if(a[i]>a[i-1]&&a[i]>a[i+1])
		{
			if(e)
			{
				nn++;
				ex[nn]=i;
				e=0;
			}
		}
	}
	if(!e)
	{
		nn--;
	}
	for(i=1;i<=nn;i++)
	{
		ms.insert(ex[i]);
	}
	for(i=1;i<=nn-1;i++)
	{
		pq.push({-abs(a[ex[i]]-a[ex[i+1]]),{ex[i],ex[i+1]}});
	}
	zs++;
	sq[zs]={0,(nn+1)/2};
	for(;!pq.empty();)
	{
		w=-pq.top().fr;
		k=pq.top().sc.fr;
		l=pq.top().sc.sc;
		pq.pop();
		if(vtd[k]||vtd[l])
		{
			continue;
		}
		zs++;
		sq[zs]={w,sq[zs-1].sc-1};
		ms.erase(k);
		ms.erase(l);
		vtd[k]=1;
		vtd[l]=1;
		it=ms.lower_bound(k);
		if(it==ms.begin())
		{
			continue;
		}
		k=*prev(it);
		it=ms.upper_bound(l);
		if(it==ms.end())
		{
			continue;
		}
		l=*it;
		pq.push({-abs(a[k]-a[l]),{k,l}});
	}
}

int max_towers(int lb,int rb,int cw)
{
	lb++;
	rb++;
	if(lb==rb)
	{
		return 1;
	}
	else
	{
		long long p;
		
		p=lower_bound(sq+1,sq+zs+1,mp((long long)cw,-inf))-sq-1;
		return sq[p].sc;
	}
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 429 ms 1280 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 336 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 336 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 739 ms 8608 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 195 ms 2100 KB Output is correct
2 Correct 919 ms 8616 KB Output is correct
3 Correct 975 ms 8720 KB Output is correct
4 Correct 974 ms 10656 KB Output is correct
5 Correct 990 ms 10700 KB Output is correct
6 Correct 980 ms 10524 KB Output is correct
7 Correct 1036 ms 10532 KB Output is correct
8 Correct 797 ms 1860 KB Output is correct
9 Correct 898 ms 1840 KB Output is correct
10 Correct 555 ms 1840 KB Output is correct
11 Correct 919 ms 1868 KB Output is correct
12 Correct 65 ms 8640 KB Output is correct
13 Correct 94 ms 10620 KB Output is correct
14 Correct 102 ms 10540 KB Output is correct
15 Correct 18 ms 1872 KB Output is correct
16 Correct 13 ms 1836 KB Output is correct
17 Correct 65 ms 7432 KB Output is correct
18 Correct 64 ms 8744 KB Output is correct
19 Correct 71 ms 8628 KB Output is correct
20 Correct 103 ms 10584 KB Output is correct
21 Correct 102 ms 10600 KB Output is correct
22 Correct 111 ms 10540 KB Output is correct
23 Correct 100 ms 10548 KB Output is correct
24 Correct 11 ms 1840 KB Output is correct
25 Correct 18 ms 1848 KB Output is correct
26 Correct 11 ms 1836 KB Output is correct
27 Correct 12 ms 1836 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
29 Correct 2 ms 464 KB Output is correct
30 Correct 2 ms 464 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 464 KB Output is correct
35 Correct 1 ms 464 KB Output is correct
36 Correct 2 ms 464 KB Output is correct
37 Correct 2 ms 464 KB Output is correct
38 Correct 2 ms 464 KB Output is correct
39 Correct 2 ms 464 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 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 336 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 429 ms 1280 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -