Submission #626529

#	Time	Username	Problem	Language	Result	Execution time	Memory
626529		haojiandan	Radio Towers (IOI22_towers)	C++17	100 / 100	1223 ms	44900 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+10;
const int maxm=maxn*40;
const int INF=2e9;
int n,h[maxn],tot,st[maxn];
int mx[maxn*4],ls[maxm],rs[maxm],tr[maxm];
void build(int l,int r,int root) {
	if (l==r) { mx[root]=h[l]; return; }
	int mid=(l+r)>>1;
	build(l,mid,root<<1),build(mid+1,r,root<<1|1);
	mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
int querymx(int L,int R,int l,int r,int root) {
	if (L>R) return -INF;
	if (L<=l&&r<=R) return mx[root];
	int mid=(l+r)>>1,res=0;
	if (L<=mid) res=querymx(L,R,l,mid,root<<1);
	if (mid<R) res=max(res,querymx(L,R,mid+1,r,root<<1|1));
	return res;
}
int L[maxn],R[maxn],rt[maxn];
namespace Seg {
	int mxR[maxn*4],mxL[maxn*4];
	void build(int l,int r,int root) {
		if (l==r) { mxR[root]=R[l],mxL[root]=L[l]; return; }
		int mid=(l+r)>>1;
		build(l,mid,root<<1),build(mid+1,r,root<<1|1);
		mxR[root]=max(mxR[root<<1],mxR[root<<1|1]);
		mxL[root]=max(mxL[root<<1],mxL[root<<1|1]);
	}
	int query1(int L,int R,int l,int r,int root,int delta) {
		if (mxR[root]<delta) return n+1;
		if (L<=l&&r<=R) {
			if (l==r) return l;
			int mid=(l+r)>>1;
			if (mxR[root<<1]>=delta) return query1(L,R,l,mid,root<<1,delta);
			return query1(L,R,mid+1,r,root<<1|1,delta);
		}
		int mid=(l+r)>>1,res=n+1;
		if (L<=mid) { res=query1(L,R,l,mid,root<<1,delta); if (res<=n) return res; }
		if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
	}
	int query2(int L,int R,int l,int r,int root,int delta) {
		if (mxL[root]<delta) return 0;
		if (L<=l&&r<=R) {
			if (l==r) return l;
			int mid=(l+r)>>1;
			if (mxL[root<<1|1]>=delta) return query2(L,R,mid+1,r,root<<1|1,delta);
			return query2(L,R,l,mid,root<<1,delta);
		}
		int mid=(l+r)>>1,res=0;
		if (mid<R) { res=query2(L,R,mid+1,r,root<<1|1,delta); if (res) return res; }
		if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
	}
};
void add(int x,int l,int r,int &root) {
	tot++; ls[tot]=ls[root],rs[tot]=rs[root],tr[tot]=tr[root]+1; root=tot;
	if (l==r) return;
	int mid=((ll)l+r)>>1;
	if (x<=mid) add(x,l,mid,ls[root]); else add(x,mid+1,r,rs[root]);
}
int query(int L,int R,int l,int r,int x,int y) {
	if (L<=l&&r<=R) return tr[y]-tr[x];
	int res=0,mid=((ll)l+r)>>1;
	if (L<=mid) res+=query(L,R,l,mid,ls[x],ls[y]);
	if (mid<R) res+=query(L,R,mid+1,r,rs[x],rs[y]);
	return res;
}
void init(int _n, vector<int> H) {
	n=_n;
	for (int i=1;i<=n;i++) h[i]=H[i-1];
	build(1,n,1);
	for (int i=1;i<=n;i++) {
		while (tot&&h[st[tot]]>h[i]) tot--;
		if (!tot) L[i]=INF; else {
			L[i]=querymx(st[tot]+1,i-1,1,n,1);
			if (L[i]>=0) L[i]-=h[i];
		}
		st[++tot]=i;
	}
	tot=0;
	for (int i=n;i>=1;i--) {
		while (tot&&h[st[tot]]>h[i]) tot--;
		if (!tot) R[i]=INF; else {
			R[i]=querymx(i+1,st[tot]-1,1,n,1);
			if (R[i]>=0) R[i]-=h[i];
		}
		st[++tot]=i;
	}
	Seg::build(1,n,1);
	for (int i=1;i<=n;i++) rt[i]=rt[i-1],add(min(L[i],R[i]),-INF,INF,rt[i]);
}
int max_towers(int l, int r, int D) {
	l++,r++;
	l=Seg::query1(l,n,1,n,1,D);
	r=Seg::query2(1,r,1,n,1,D);
	if (l>r) return 1;
	//printf("%d %d\n",l,r);
	return 2+(l+1<=r-1?query(D,INF,-INF,INF,rt[l],rt[r-1]):-1);
}

Compilation message (stderr)

towers.cpp: In function 'int Seg::query1(int, int, int, int, int, int)':
towers.cpp:44:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |   if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
      |   ^~
towers.cpp:44:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |   if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
      |                                                       ^~~~~~
towers.cpp: In function 'int Seg::query2(int, int, int, int, int, int)':
towers.cpp:56:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |   if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
      |   ^~
towers.cpp:56:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |   if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
      |                                                    ^~~~~~

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