Submission #404073

#	Time	Username	Problem	Language	Result	Execution time	Memory
404073		keta_tsimakuridze	Two Antennas (JOI19_antennas)	C++14	100 / 100	1473 ms	78012 KiB

antennas

#include<bits/stdc++.h>
#define f first
#define s second
#define remove rem
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7,Inf=1e17;
int t,lazy[4*N],l[N],r[N],a[N],b[N],h[N],n,Q,ans[N];
string s;
vector<pair<int,int> >q[N];
vector<int>add[2*N],remove[2*N];
pair<int,int> tree[4*N];
void build(int u,int l,int r){
	tree[u].f=Inf;
	tree[u].s=-Inf;
	lazy[u]=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
}
void update(int u,int start,int end,int l,int r,int val,int type) {
	if(lazy[u]) {
		tree[u].s = max(tree[u].s,lazy[u]-tree[u].f);
		if(l!=r){
			lazy[2*u]=max(lazy[2*u],lazy[u]);
			lazy[2*u+1]=max(lazy[2*u+1],lazy[u]);
		}
		lazy[u] = 0;
	}
	if(l>end || r<start) return;
	if(start<=l && r<=end)  {
		if(type==0) {
			tree[u].f = val;
			return;
		}
		lazy[u]=val;
		tree[u].s = max(tree[u].s,lazy[u]-tree[u].f);
		if(l!=r){
			lazy[2*u]=max(lazy[2*u],lazy[u]);
			lazy[2*u+1]=max(lazy[2*u+1],lazy[u]);
		}
		lazy[u] = 0;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,start,end,l,mid,val,type);
	update(2*u+1,start,end,mid+1,r,val,type);
	tree[u].f = min(tree[2*u].f,tree[2*u+1].f);
	tree[u].s = max(tree[2*u].s,tree[2*u+1].s);
}
int getans(int u,int start,int end,int l,int r){
	if(lazy[u]) {
		tree[u].s = max(tree[u].s,lazy[u]-tree[u].f);
		if(l!=r){
			lazy[2*u]=max(lazy[2*u],lazy[u]);
			lazy[2*u+1]=max(lazy[2*u+1],lazy[u]);
		}
		lazy[u] = 0;
	}
	if(l>end || r<start) return -Inf;
	if(start<=l && r<=end) return tree[u].s;
	int mid=(l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
void go(){
	for(int i=1;i<=n;i++){
		add[i+a[i]].push_back(i); 
		remove[i+b[i]+1].push_back(i);
		for(int j=0;j<add[i].size();j++) { 
			update(1,add[i][j],add[i][j],1,n,h[add[i][j]],0);
		}
		add[i].clear();
		for(int j=0;j<remove[i].size();j++) { 
			update(1,remove[i][j],remove[i][j],1,n,Inf,0);
		}
		remove[i].clear();
		update(1,max(1ll,i-b[i]),i-a[i],1,n,h[i],1);
		for(int j=0;j<q[i].size();j++) {
			ans[q[i][j].s] = max(ans[q[i][j].s],getans(1,q[i][j].f,i,1,n));
		}
		q[i].clear();
	}
}
 main(){
	// t=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i]>>a[i]>>b[i];
	}
	cin>>Q;
	for(int i=1;i<=Q;i++){
		cin>>l[i]>>r[i]; ans[i]=-Inf;
		q[r[i]].push_back({l[i],i});
	}
	build(1,1,n);
	go(); 
	reverse(h+1,h+n+1);
	reverse(a+1,a+n+1);
	reverse(b+1,b+n+1);
	build(1,1,n);
	for(int i=1;i<=Q;i++){
		q[n-l[i]+1].push_back({n-r[i]+1,i});
	}
	go(); 
	for(int i=1;i<=Q;i++) if(ans[i] < 0) cout<<-1<<"\n"; else cout<<ans[i]<<"\n";
}

Compilation message (stderr)

antennas.cpp: In function 'void go()':
antennas.cpp:70:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int j=0;j<add[i].size();j++) {
      |               ~^~~~~~~~~~~~~~
antennas.cpp:74:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j=0;j<remove[i].size();j++) {
      |               ~^~~~~~~~~~~~~~~~~
antennas.cpp:79:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int j=0;j<q[i].size();j++) {
      |               ~^~~~~~~~~~~~
antennas.cpp: At global scope:
antennas.cpp:85:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 |  main(){
      |  ^~~~

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