Submission #240298

#	Time	Username	Problem	Language	Result	Execution time	Memory
240298		kshitij_sodani	Two Antennas (JOI19_antennas)	C++17	0 / 100	3097 ms	382444 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n;
llo it[200001];
pair<llo,llo> aa[200001];

vector<pair<llo,llo>> pre[200001];
llo tree[800001];//max values
multiset<pair<pair<llo,llo>,llo>> tree2[800001];//valid segments
multiset<llo> tree3[800001];//current valid heights
multiset<llo> tree5[800001];//current valid heights

vector<pair<llo,llo>> lazy[800001];//lazy
vector<pair<pair<llo,llo>,llo>> tree4[800001];
llo pollo[800001];
llo ans[200001];
bool cmp(pair<pair<llo,llo>,llo> d,pair<pair<llo,llo>,llo> e){
	return d.a.b<e.a.b;
}
void push(llo no,llo bet,llo val){
//	cout<<no<<"::"<<bet<<"::"<<val<<endl;

	while(pollo[no]>=0){
		if(tree4[no][pollo[no]].a.b>=bet){
			tree3[no].insert(tree4[no][pollo[no]].b);
			tree5[no].insert(-tree4[no][pollo[no]].b);
			tree2[no].insert({{-tree4[no][pollo[no]].a.a,tree4[no][pollo[no]].a.b},tree4[no][pollo[no]].b});
			//tree2[no].insert(tree4[no][pollo[no]]);
			pollo[no]--;
		}
		else{
			break;
		}
	}
	while(tree2[no].size()){
		
		if(-(*tree2[no].begin()).a.a>bet){
			auto k=tree3[no].find((*tree2[no].begin()).b);
			tree3[no].erase(k);
			auto kk=tree5[no].find(-(*tree2[no].begin()).b);
			tree5[no].erase(kk);
			//auto k=tree2[no].find((*tree2[no].end()));
			tree2[no].erase(tree2[no].begin());
		}
		else{
			break;
		}
	}
	/*for(auto j:tree2[no]){
		cout<<j.a.a<<","<<j.a.b<<","<<j.b<<endl;
	}*/
	if(tree3[no].size()){
/*		auto j=tree3[no].end();
		j--;*/
		tree[no]=max(tree[no],abs((-(*tree5[no].begin()))-val));
		tree[no]=max(tree[no],abs((*tree3[no].begin())-val));
	}

}
void build(llo no,llo l,llo r){
	tree[no]=-1;
	if(l==r){
		tree4[no].pb({{l-aa[l].b,l-aa[l].a},it[l]});
	//	cout<<l<<","<<l-aa[l].b<<','<<l-aa[l].a<<','<<it[l]<<endl;

	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree4[no]=tree4[no*2+1];
		for(auto j:tree4[no*2+2]){
			tree4[no].pb(j);
		}
		sort(tree4[no].begin(),tree4[no].end(),cmp);
		
	}
/*	cout<<l<<",,"<<r<<endl;
	for(auto j:tree4[no]){
		cout<<j.a.a<<" "<<j.a.b<<" "<<j.b<<endl;
	}*/
	pollo[no]=(llo)(tree4[no].size())-1;
}

void update(llo no,llo l,llo r,llo aa,llo bb,llo le,llo val){
	for(llo i=0;i<lazy[no].size();i++){
		push(no,lazy[no][i].a,lazy[no][i].b);
		if(l<r){
			lazy[no*2+1].pb(lazy[no][i]);
		//	lazy[no*2+2].pb(lazy[no][i]);
		}
	}
	lazy[no].clear();
	if(bb<l or aa>r or l>r){
		return;
	}
	if(aa<=l and r<=bb){
	//	cout<<l<<"   "<<r<<" "<<le<<" "<<val<<endl;
		push(no,le,val);
		if(l<r){
			lazy[no*2+1].pb({le,val});
		//	lazy[no*2+2].pb({le,val});
		}
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,le,val);
		update(no*2+2,mid+1,r,aa,bb,le,val);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
	for(llo i=0;i<lazy[no].size();i++){
		push(no,lazy[no][i].a,lazy[no][i].b);
		if(l<r){
			lazy[no*2+1].pb(lazy[no][i]);
			lazy[no*2+2].pb(lazy[no][i]);
		}
	}
	lazy[no].clear();
	if(bb<l or aa>r or l>r){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		llo mid=(l+r)/2;
		llo x=query(no*2+1,l,mid,aa,bb);
		llo y=query(no*2+2,mid+1,r,aa,bb);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
		return max(x,y);		
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i]>>aa[i].a>>aa[i].b;
	}
	llo q;
	cin>>q;
	for(llo i=0;i<q;i++){
		llo bb,cc;
		cin>>bb>>cc;
		pre[bb-1].pb({cc-1,i});
	}
	build(0,0,n-1);
	for(llo i=n-1;i>=0;i--){
		if(aa[i].a+i<n){

			update(0,0,n-1,aa[i].a+i,min(aa[i].b+i,n-1),i,it[i]);
		//	cout<<i<<"::"<<aa[i].a+i<<","<<min(aa[i].b+i,n-1)<<endl;
		}
		for(auto j:pre[i]){
			ans[j.b]=query(0,0,n-1,i,j.a);
		}
	}
	for(llo i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}





	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void update(llo, llo, llo, llo, llo, llo, llo)':
antennas.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=0;i<lazy[no].size();i++){
              ~^~~~~~~~~~~~~~~~
antennas.cpp: In function 'llo query(llo, llo, llo, llo, llo)':
antennas.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=0;i<lazy[no].size();i++){
              ~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65