제출 #240291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240291		kshitij_sodani	Two Antennas (JOI19_antennas)	C++17	0 / 100	3098 ms	320156 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'
int n;
int it[200001];
pair<int,int> aa[200001];

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

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

	while(point[no]>=0){
		if(tree4[no][point[no]].a.b>=bet){
			tree3[no].insert(tree4[no][point[no]].b);
			tree5[no].insert(-tree4[no][point[no]].b);
			tree2[no].insert({{-tree4[no][point[no]].a.a,tree4[no][point[no]].a.b},tree4[no][point[no]].b});
			//tree2[no].insert(tree4[no][point[no]]);
			point[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(int no,int l,int 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{
		int 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;
	}*/
	point[no]=(int)(tree4[no].size())-1;
}

void update(int no,int l,int r,int aa,int bb,int le,int val){
	for(int 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].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});
		}
	}
	else{
		int 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]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	for(int 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].clear();
	if(bb<l or aa>r or l>r){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	else{
		int mid=(l+r)/2;
		int x=query(no*2+1,l,mid,aa,bb);
		int 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(int i=0;i<n;i++){
		cin>>it[i]>>aa[i].a>>aa[i].b;
	}
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int bb,cc;
		cin>>bb>>cc;
		pre[bb-1].pb({cc-1,i});
	}
	build(0,0,n-1);
	for(int 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(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}





	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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