oj.uz

Submission #987167

# Submission time Handle Problem Language Result Execution time Memory
987167 2024-05-22T07:43:44 Z Pyqe Radio Towers (IOI22_towers) C++17
17 / 100
 1031 ms 171036 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 n,udn=0,a[100069],uds[100069],sp[17][100069],lg2[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;
bitset<100069> spc;

struct segtree
{
	long long l,r,sm;
	pair<long long,long long> mxl,mxr;
	segtree *p[2];
	
	void bd(long long lb,long long rb)
	{
		l=lb;
		r=rb;
		if(l==r)
		{
			sm=spc[l];
			mxl={spc[l],-l};
			mxr={spc[l],l};
		}
		else
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
			sm=p[0]->sm+p[1]->sm;
			mxl=max(p[0]->mxl,p[1]->mxl);
			mxr=max(p[0]->mxr,p[1]->mxr);
		}
	}
	void ud(long long x,long long w)
	{
		if(l>=x&&r<=x)
		{
			sm+=w;
			mxl.fr+=w;
			mxr.fr+=w;
		}
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				if(!(p[ii]->l>x||p[ii]->r<x))
				{
					segtree *tmp=p[ii];
					
					p[ii]=new segtree;
					*p[ii]=*tmp;
					p[ii]->ud(x,w);
				}
			}
			sm=p[0]->sm+p[1]->sm;
			mxl=max(p[0]->mxl,p[1]->mxl);
			mxr=max(p[0]->mxr,p[1]->mxr);
		}
	}
	long long qrs(long long lb,long long rb)
	{
		if(l>rb||r<lb)
		{
			return 0;
		}
		else if(l>=lb&&r<=rb)
		{
			return sm;
		}
		else
		{
			return p[0]->qrs(lb,rb)+p[1]->qrs(lb,rb);
		}
	}
	pair<long long,long long> qrxl(long long lb,long long rb)
	{
		if(l>rb||r<lb)
		{
			return {-inf,-1};
		}
		else if(l>=lb&&r<=rb)
		{
			return mxl;
		}
		else
		{
			return max(p[0]->qrxl(lb,rb),p[1]->qrxl(lb,rb));
		}
	}
	pair<long long,long long> qrxr(long long lb,long long rb)
	{
		if(l>rb||r<lb)
		{
			return {-inf,-1};
		}
		else if(l>=lb&&r<=rb)
		{
			return mxr;
		}
		else
		{
			return max(p[0]->qrxr(lb,rb),p[1]->qrxr(lb,rb));
		}
	}
}
sg[100069];

inline void spbd()
{
	long long i,j,k;
	
	for(i=1;i<=n;i++)
	{
		sp[0][i]=a[i];
	}
	for(i=1;1ll<<i<=n;i++)
	{
		for(j=1;j<=n-(1ll<<i)+1;j++)
		{
			sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
		}
	}
	for(i=1;i<=n;i++)
	{
		for(k=i;k>1;k/=2,lg2[i]++);
	}
}

inline long long spqr(long long lb,long long rb)
{
	long long e=lg2[rb-lb+1];
	
	return min(sp[e][lb],sp[e][rb-(1ll<<e)+1]);
}

void init(int on,vector<int> aa)
{
	long long i,k,l=-1,w,k2,l2;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
	}
	ms.insert(-inf);
	ms.insert(inf);
	for(i=1;i<=n;i++)
	{
		if(((i==1||a[i]<a[i-1])&&(i==n||a[i]<a[i+1]))||(i>1&&i<n&&a[i]>max(a[i-1],a[i+1])))
		{
			ms.insert(i);
			if(l!=-1)
			{
				rg.insert({abs(a[l]-a[i]),{l,i}});
			}
			l=i;
			spc[i]=1;
		}
	}
	sg[0].bd(1,n);
	for(;!rg.empty();)
	{
		w=rg.begin()->fr;
		k=rg.begin()->sc.fr;
		l=rg.begin()->sc.sc;
		rg.erase(rg.begin());
		if(ms.find(k)==ms.end()||ms.find(l)==ms.end())
		{
			continue;
		}
		ms.erase(k);
		ms.erase(l);
		k2=*prev(ms.lower_bound(k));
		l2=*ms.upper_bound(l);
		if(k2!=-inf&&l2!=inf)
		{
			rg.insert({abs(a[k2]-a[l2]),{k2,l2}});
		}
		udn++;
		uds[udn]=w;
		sg[udn]=sg[udn-1];
		sg[udn].ud(k,-1);
		sg[udn].ud(l,-1);
	}
	spbd();
}

int max_towers(int lb,int rb,int cw)
{
	long long k,w,w2,w3,p,mn,z;
	pair<long long,long long> tmp;
	
	lb++;
	rb++;
	p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
	w=sg[p].sm;
	w2=sg[p].qrs(1,lb-1);
	w3=sg[p].qrs(rb+1,n);
	z=(max(w-(w2+1)/2*2-(w3+1)/2*2,0ll)+1)/2;
	if(w2%2)
	{
		tmp=sg[p].qrxl(lb,rb);
		if(tmp.fr)
		{
			k=-tmp.sc;
			mn=spqr(lb,k-1);
			z+=a[k]-mn>=cw;
		}
	}
	if(w3%2)
	{
		tmp=sg[p].qrxr(lb,rb);
		if(tmp.fr)
		{
			k=tmp.sc;
			mn=spqr(k+1,rb);
			z+=a[k]-mn>=cw;
		}
	}
	z=max(z,1ll);
	return z;
}

Compilation message

towers.cpp: In function 'void spbd()':
towers.cpp:134:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  134 |    sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
      |                                            ~^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 25176 KB Output is correct
2 Correct 817 ms 37628 KB Output is correct
3 Correct 803 ms 37808 KB Output is correct
4 Correct 860 ms 37592 KB Output is correct
5 Correct 790 ms 37596 KB Output is correct
6 Incorrect 780 ms 37836 KB 11314th lines differ - on the 1st token, expected: '1', found: '2'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 32892 KB Output is correct
2 Correct 847 ms 126404 KB Output is correct
3 Correct 770 ms 126156 KB Output is correct
4 Correct 1004 ms 171036 KB Output is correct
5 Correct 978 ms 170632 KB Output is correct
6 Correct 986 ms 170948 KB Output is correct
7 Correct 1031 ms 170480 KB Output is correct
8 Correct 555 ms 37712 KB Output is correct
9 Correct 566 ms 37720 KB Output is correct
10 Correct 613 ms 37848 KB Output is correct
11 Correct 623 ms 37588 KB Output is correct
12 Correct 257 ms 126404 KB Output is correct
13 Correct 434 ms 170436 KB Output is correct
14 Correct 446 ms 170936 KB Output is correct
15 Correct 34 ms 37584 KB Output is correct
16 Correct 36 ms 37584 KB Output is correct
17 Correct 286 ms 122228 KB Output is correct
18 Correct 279 ms 126420 KB Output is correct
19 Correct 280 ms 126468 KB Output is correct
20 Correct 457 ms 170440 KB Output is correct
21 Correct 455 ms 170752 KB Output is correct
22 Correct 441 ms 170436 KB Output is correct
23 Correct 487 ms 170492 KB Output is correct
24 Correct 35 ms 37680 KB Output is correct
25 Correct 33 ms 37596 KB Output is correct
26 Correct 33 ms 37852 KB Output is correct
27 Correct 34 ms 37584 KB Output is correct
28 Correct 6 ms 9048 KB Output is correct
29 Correct 8 ms 9816 KB Output is correct
30 Correct 7 ms 9836 KB Output is correct
31 Correct 4 ms 8024 KB Output is correct
32 Correct 4 ms 8024 KB Output is correct
33 Correct 5 ms 8280 KB Output is correct
34 Correct 6 ms 9048 KB Output is correct
35 Correct 7 ms 9048 KB Output is correct
36 Correct 7 ms 9816 KB Output is correct
37 Correct 7 ms 9816 KB Output is correct
38 Correct 7 ms 9816 KB Output is correct
39 Correct 7 ms 9816 KB Output is correct
40 Correct 5 ms 8024 KB Output is correct
41 Correct 5 ms 8024 KB Output is correct
42 Correct 4 ms 8024 KB Output is correct
43 Correct 4 ms 8024 KB Output is correct

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 25176 KB Output is correct
2 Correct 817 ms 37628 KB Output is correct
3 Correct 803 ms 37808 KB Output is correct
4 Correct 860 ms 37592 KB Output is correct
5 Correct 790 ms 37596 KB Output is correct
6 Incorrect 780 ms 37836 KB 11314th lines differ - on the 1st token, expected: '1', found: '2'
7 Halted 0 ms 0 KB -