Submission #803965

#	Time	Username	Problem	Language	Result	Execution time	Memory
803965		kshitij_sodani	Radio Towers (IOI22_towers)	C++17	23 / 100	4029 ms	22412 KiB

towers

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "towers.h"

#include <vector>
int st=0;
int n;
vector<int> it;
int tree[4*200001][2];
void build(int no,int l,int r){
	if(l==r){
		tree[no][0]=it[l];
		tree[no][1]=it[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return 1e9+1;
	}
	if(aa<=l and r<=bb){
		return tree[no][0];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int query2(int no,int l,int r,int aa,int bb){
	if(r<aa or l>bb or aa>bb){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no][1];
	}
	int mid=(l+r)/2;
	return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
vector<int> mm;

void init(int nn, vector<int> ita) {
	n=nn;
	it=ita;
	st=0;
	build(0,0,n-1);
	
}
int le[100001];
int re2[100001];
int cc[100001][20];
int dd[100001][20];
int val[100001];
void rec(int l,int r){
	mm.clear();
	vector<pair<llo,llo>> ss;
	for(int i=r;i>=l;i--){
		while(ss.size()){
			if(ss.back().a<=it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		re2[i]=n;
		if(ss.size()){
			re2[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
	ss.clear();
	for(int i=l;i<=r;i++){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		le[i]=-1;
		if(ss.size()){
			le[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
	for(int i=0;i<n;i++){
		int x=it[i]-query(0,0,n-1,le[i]+1,i);
		int y=it[i]-query(0,0,n-1,i,re2[i]-1);
		val[i]=min(x,y);
		mm.pb(min(x,y));
	}
	for(int i=0;i<n;i++){
		cc[i][0]=le[i];
		dd[i][0]=re2[i];
	//	cout<<i<<":"<<le[i]<<endl;
	//	cout<<i<<":"<<re2[i]<<endl;
		if(re2[i]==n){
			dd[i][0]=-1;
		}
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(cc[i][j-1]==-1){
				cc[i][j]=-1;
			}
			else{
				cc[i][j]=cc[cc[i][j-1]][j-1];
			}
		}
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(dd[i][j-1]==-1){
				dd[i][j]=-1;
			}
			else{
				dd[i][j]=dd[dd[i][j-1]][j-1];
			}
		}
	}
	sort(mm.begin(),mm.end());

}

set<pair<int,int>> xx[2];
vector<pair<pair<int,int>,int>> yy;
map<int,int> kk;
int max_towers(int l, int r, int d) {

	if(st==0){
		rec(0,n-1);
		st=1;
	}
	//cout<<dd[0][0]<<"???"<<endl;
	llo low=mm.size();
	llo su=0;
	for(int i=l;i<=r;i++){
		if(val[i]>=d){
			su++;
		}
	}
	int ind=-1;
	for(int i=l;i<=r;i++){
		if(cc[i][0]<l){
			ind=i;
			break;
		}
	}
	int ind2=ind;
	for(int j=19;j>=0;j--){
		if(dd[ind2][j]<=r and dd[ind2][j]>=0){
			ind2=dd[ind2][j];
		}
	}
	vector<llo> ss;
	int ind3=-1;
	if(query(0,0,n-1,l,ind-1)>it[ind]-d){
		for(int j=19;j>=0;j--){
			if(dd[ind][j]<=r and dd[ind][j]>=0){
				if(query(0,0,n-1,l,dd[ind][j]-1)>it[dd[ind][j]]-d){
					ind=dd[ind][j];
				}
			}
		}
		ind3=ind;

		while(true){
			ss.pb(ind3);
			if(ind3==ind){
				break;
			}
			ind3=dd[ind3][0];
		}
	}
	pair<int,int> ll={ind3,ind};

	//from ind3 to ind


	//return su;
	vector<int> tt;
	ind=-1;
	for(int i=r;i>=l;i--){
		if(dd[i][0]>r or dd[i][0]==-1){
			ind=i;
			break;
		}
	}
	ind3=-1;
	if(query(0,0,n-1,ind+1,r)<=it[ind]-d){
	}
	else{
		ind3=ind;
		for(int j=19;j>=0;j--){
			if(cc[ind][j]>=l){
				if(query(0,0,n-1,cc[ind][j]+1,r)>it[cc[ind][j]]-d){
					ind=cc[ind][j];
				}
			}
		}
		while(true){
			tt.pb(ind3);
			if(ind3==ind){
				break;
			}
			ind3=cc[ind3][0];
		}
	}
	pair<int,int> rr={ind3,ind};
	for(auto j:ss){
		if(val[j]>=d){
			su--;
		}
	}
	for(auto j:tt){
		if(val[j]>=d){
			su--;
		}
	}
	if(ll.a>=0 and rr.a>=0){
		if(rr.b==ind2 and ll.b==ind2){
			if(val[rr.b]>=d){
				su--;
			}
		}
	}
	
	su++;
	return su;
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:144:6: warning: unused variable 'low' [-Wunused-variable]
  144 |  llo low=mm.size();
      |      ^~~

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