Submission #337344

#	Time	Username	Problem	Language	Result	Execution time	Memory
337344		alishahali1382	Two Antennas (JOI19_antennas)	C++14	100 / 100	673 ms	51168 KiB

antennas

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
int H[MAXN], A[MAXN], B[MAXN], L[MAXN], ans[MAXN];
int lazymn[MAXN<<2], lazymx[MAXN<<2];
int seg[MAXN<<2], Mn[MAXN<<2], Mx[MAXN<<2];
bool alive[MAXN];
vector<int> V1[MAXN], V2[MAXN], Q[MAXN];

inline void add_lazy(int id, int mn, int mx){
	seg[id]=max(seg[id], mx-Mn[id]);
	seg[id]=max(seg[id], Mx[id]-mn);
	lazymn[id]=min(lazymn[id], mn);
	lazymx[id]=max(lazymx[id], mx);
}
inline void shift(int id){
	if (lazymn[id]>lazymx[id]) return ;
	add_lazy(id<<1, lazymn[id], lazymx[id]);
	add_lazy(id<<1 | 1, lazymn[id], lazymx[id]);
	lazymn[id]=inf, lazymx[id]=-inf;
}
void Set(int id, int tl, int tr, int pos){
	if (pos<tl || tr<=pos) return ;
	if (tr-tl==1){
		if (alive[pos]) Mn[id]=Mx[id]=H[pos];
		else Mn[id]=inf, Mx[id]=-inf;
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Set(id<<1, tl, mid, pos);
	Set(id<<1 | 1, mid, tr, pos);
	Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
	Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
	seg[id]=max(seg[id<<1], seg[id<<1 | 1]);
}
void Update(int id, int tl, int tr, int l, int r, int val){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		add_lazy(id, val, val);
//		debug2(id, val)
//		debug(seg[id])
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Update(id<<1, tl, mid, l, r, val);
	Update(id<<1 | 1, mid, tr, l, r, val);
	Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
	Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
	seg[id]=max(seg[id<<1], seg[id<<1 | 1]);
}
int Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return -1;
	if (l<=tl && tr<=r) return seg[id];
	shift(id);
	int mid=(tl+tr)>>1;
	return max(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>H[i]>>A[i]>>B[i];
		V1[min(n+1, i+A[i])].pb(i);
		V2[min(n, i+B[i])+1].pb(i);
	}
	cin>>m;
	for (int i=1; i<=m; i++){
		cin>>L[i]>>x;
		Q[x].pb(i);
	}
	memset(lazymn, 63, sizeof(lazymn));
	memset(lazymx, -63, sizeof(lazymx));
	memset(Mn, 63, sizeof(Mn));
	memset(Mx, -63, sizeof(Mx));
	memset(seg, -1, sizeof(seg));
//	debugv(V1[2])
//	debugv(V2[2])
	for (int r=1; r<=n; r++){
		for (int i:V1[r]) alive[i]=1, Set(1, 1, n+1, i);
		for (int i:V2[r]) alive[i]=0, Set(1, 1, n+1, i);
		Update(1, 1, n+1, r-B[r], r-A[r]+1, H[r]);
		for (int i:Q[r]) ans[i]=Get(1, 1, n+1, L[i], r+1);
	}
	for (int i=1; i<=m; i++) cout<<ans[i]<<"\n";
	
	return 0;
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

2
10 2 4
1 1 1
1
1 2


*/

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