oj.uz

Submission #835080

# Submission time Handle Problem Language Result Execution time Memory
835080 2023-08-23T07:48:25 Z ttamx Radio Towers (IOI22_towers) C++17
17 / 100
 896 ms 111964 KB 
#include "towers.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p2;

const int N=1e5+5;
const int K=1<<18;
const int LG=17;
const int inf=2e9;

int n;
int h[N],spmx[LG][N],spmn[LG][N];
vector<pair<int,int>> vec;

struct persist{
	struct info{
		int mn,mx,val;
		info():mn(inf),mx(-inf),val(0){}
		info(int x):mn(x),mx(x),val(1){}
		friend info operator+(info a,info b){
			info c;
			c.mn=min(a.mn,b.mn);
			c.mx=max(a.mx,b.mx);
			c.val=a.val+b.val;
			return c;
		}
	};
	struct node;
	typedef node* pnode;
	struct node{
		info val;
		pnode l,r;
		node():val(),l(nullptr),r(nullptr){}
	};
	pnode rt[N];
	void build(int l,int r,pnode &t){
		t=new node();
		if(l==r)return;
		int m=(l+r)/2;
		build(l,m,t->l);
		build(m+1,r,t->r);
	}
	void build(int t){
		build(1,n,rt[t]);
	}
	void update(int l,int r,pnode &t,pnode k,int x){
		t=new node(*k);
		t->val=t->val+info(x);
		if(l==r)return;
		int m=(l+r)/2;
		if(x<=m)update(l,m,t->l,k->l,x);
		else update(m+1,r,t->r,k->r,x);
	}
	void update(int k,int t,int x){
		update(1,n,rt[t],rt[k],x);
	}
	info query(int l,int r,pnode t,int x,int y){
		if(y<l||r<x)return info();
		if(x<=l&&r<=y)return t->val;
		int m=(l+r)/2;
		return query(l,m,t->l,x,y)+query(m+1,r,t->r,x,y);
	}
	info query(int t,int x,int y){
		return query(1,n,rt[t],x,y);
	}
}pst;

struct segtree{
	struct node{
		int mn,mx,vl,vr;
		node(int x=0):mn(x),mx(x),vl(0),vr(0){}
		friend node operator+(node a,node b){
			node c;
			c.mn=min(a.mn,b.mn);
			c.mx=max(a.mx,b.mx);
			c.vl=max({a.vl,b.vl,b.mx-a.mn});
			c.vr=max({a.vr,b.vr,a.mx-b.mn});
			return c;
		}
	}t[K];
	void build(int l,int r,int i){
		if(l==r)return void(t[i]=node(h[l]));
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
		t[i]=t[i*2]+t[i*2+1];
	}
	void build(){
		build(1,n,1);
	}
	node query(int l,int r,int i,int x,int y){
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		if(y<=m)return query(l,m,i*2,x,y);
		if(m<x)return query(m+1,r,i*2+1,x,y);
		return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y);
	}
	node query(int x,int y){
		return query(1,n,1,x,y);
	}
}s;

int rmxq(int l,int r){
	int k=31-__builtin_clz(r-l+1);
	return max(spmx[k][l],spmx[k][r-(1<<k)+1]);
}

int rmnq(int l,int r){
	int k=31-__builtin_clz(r-l+1);
	return min(spmn[k][l],spmn[k][r-(1<<k)+1]);
}

void init(int N,vector<int> H){
	n=N;
	for(int i=1;i<=n;i++)h[i]=H[i-1];
	h[0]=h[n+1]=inf;
	for(int i=0;i<=n+1;i++)spmx[0][i]=spmn[0][i]=h[i];
	for(int i=1;i<LG;i++){
		for(int j=0;j+(1<<i)-1<=n+1;j++){
			spmx[i][j]=max(spmx[i-1][j],spmx[i-1][j+(1<<(i-1))]);
			spmn[i][j]=min(spmn[i-1][j],spmn[i-1][j+(1<<(i-1))]);
		}
	}
	auto lb=[&](int id){
		int l=0,r=id-1;
		while(l<r){
			int m=(l+r+1)/2;
			if(rmnq(m,id)<h[id])l=m;
			else r=m-1;
		}
		return l;
	};
	auto ub=[&](int id){
		int l=id+1,r=n+1;
		while(l<r){
			int m=(l+r)/2;
			if(rmnq(id,m)<h[id])r=m;
			else l=m+1;
		}
		return l;
	};
	for(int i=1;i<=n;i++){
		int l=lb(i),r=ub(i);
		int d=min(rmxq(l,i),rmxq(i,r))-h[i];
		vec.emplace_back(d,i);
	}
	vec.emplace_back(-inf,-1);
	sort(vec.begin(),vec.end());
	pst.build(n+1);
	for(int i=n;i>=1;i--){
		pst.update(i+1,i,vec[i].second);
	}
	s.build();
}

int max_towers(int L,int R,int D){
	L++,R++;
	auto lb=[&](int id){
		int l=L-1,r=id-1;
		while(l<r){
			int m=(l+r+1)/2;
			if(rmxq(m,id)>=h[id]+D)l=m;
			else r=m-1;
		}
		return l;
	};
	auto ub=[&](int id){
		int l=id+1,r=R+1;
		while(l<r){
			int m=(l+r)/2;
			if(rmxq(id,m)>=h[id]+D)r=m;
			else l=m+1;
		}
		return l;
	};
	int ver=lower_bound(vec.begin(),vec.end(),p2(D,0))-vec.begin();
	auto res=pst.query(ver,L,R);
	if(res.val==0)return L==R?1:2;
	int l=lb(res.mn),r=ub(res.mx),ans=res.val;
	if(L<l&&s.query(L,l).vl>=D)ans++;
	if(r<R&&s.query(r,R).vr>=D)ans++;
	return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 423 ms 66036 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 Correct 2 ms 4688 KB Output is correct
2 Correct 3 ms 5968 KB Output is correct
3 Correct 4 ms 6004 KB Output is correct
4 Correct 3 ms 5968 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 3 ms 6036 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Incorrect 4 ms 6040 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 3 ms 5968 KB Output is correct
3 Correct 4 ms 6004 KB Output is correct
4 Correct 3 ms 5968 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 3 ms 6036 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Incorrect 4 ms 6040 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 27472 KB Output is correct
2 Correct 817 ms 111928 KB Output is correct
3 Correct 659 ms 111912 KB Output is correct
4 Correct 892 ms 111856 KB Output is correct
5 Correct 878 ms 111900 KB Output is correct
6 Correct 824 ms 111896 KB Output is correct
7 Correct 849 ms 111916 KB Output is correct
8 Correct 707 ms 111872 KB Output is correct
9 Correct 625 ms 111892 KB Output is correct
10 Correct 707 ms 111936 KB Output is correct
11 Correct 896 ms 111884 KB Output is correct
12 Correct 125 ms 111916 KB Output is correct
13 Correct 125 ms 111864 KB Output is correct
14 Correct 127 ms 111948 KB Output is correct
15 Correct 108 ms 111920 KB Output is correct
16 Correct 109 ms 111888 KB Output is correct
17 Correct 119 ms 108112 KB Output is correct
18 Correct 142 ms 111892 KB Output is correct
19 Correct 118 ms 111932 KB Output is correct
20 Correct 128 ms 111964 KB Output is correct
21 Correct 129 ms 111924 KB Output is correct
22 Correct 122 ms 111916 KB Output is correct
23 Correct 125 ms 111892 KB Output is correct
24 Correct 99 ms 111928 KB Output is correct
25 Correct 106 ms 111932 KB Output is correct
26 Correct 112 ms 111912 KB Output is correct
27 Correct 115 ms 111904 KB Output is correct
28 Correct 4 ms 5968 KB Output is correct
29 Correct 3 ms 5968 KB Output is correct
30 Correct 4 ms 6020 KB Output is correct
31 Correct 3 ms 5968 KB Output is correct
32 Correct 4 ms 5968 KB Output is correct
33 Correct 4 ms 5072 KB Output is correct
34 Correct 5 ms 5968 KB Output is correct
35 Correct 5 ms 5968 KB Output is correct
36 Correct 3 ms 5968 KB Output is correct
37 Correct 3 ms 5968 KB Output is correct
38 Correct 3 ms 5968 KB Output is correct
39 Correct 3 ms 5968 KB Output is correct
40 Correct 3 ms 5968 KB Output is correct
41 Correct 3 ms 5968 KB Output is correct
42 Correct 3 ms 5968 KB Output is correct
43 Correct 3 ms 6024 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 3 ms 5968 KB Output is correct
3 Correct 4 ms 6004 KB Output is correct
4 Correct 3 ms 5968 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 3 ms 6036 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Incorrect 4 ms 6040 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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