Submission #829528

#	Time	Username	Problem	Language	Result	Execution time	Memory
829528		MohamedAhmed04	Two Antennas (JOI19_antennas)	C++14	100 / 100	638 ms	46856 KiB

antennas

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX] , a[MAX] , b[MAX] ;
int n , q ;

int L[MAX] , R[MAX] ;

vector<int>ins[MAX] , del[MAX] ;
vector< pair<int , int> >queries[MAX] ;

int tree[4 * MAX] , lazy[4 * MAX] , val[4 * MAX] ;

void build(int node , int l , int r)
{
	tree[node] = val[node] = -1e9 - 10 , lazy[node] = 0 ;
	if(l == r)
		return ;
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid+1 , r) ;
}

void prop(int node , int l , int r)
{
	val[node] = max(val[node] , tree[node] + lazy[node]) ;
	if(l != r)
	{
		lazy[node << 1] = max(lazy[node << 1] , lazy[node]) ;
		lazy[node << 1 | 1] = max(lazy[node << 1 | 1] , lazy[node]) ;
	}
	lazy[node] = 0 ;
}

void update(int node , int l , int r , int idx , int x)
{
	prop(node , l , r) ;
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[node] = x ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , x) ;
	update(node << 1 | 1 , mid+1 , r , idx , x) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}

void update2(int node , int l , int r , int from , int to , int x)
{
	prop(node , l , r) ;
	if(from > r || to < l || from > to)
		return ;
	if(l >= from && r <= to)
	{
		lazy[node] = x ;
		prop(node , l , r) ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update2(node << 1 , l , mid , from , to , x) ;
	update2(node << 1 | 1 , mid+1 , r , from , to , x) ;
	val[node] = max({val[node] , val[node << 1] , val[node << 1 | 1]}) ;
}

int query(int node , int l , int r , int from , int to)
{
	prop(node , l , r) ;
	if(from > r || to < l || from > to)
		return (-1e9 - 10) ;
	if(l >= from && r <= to)
		return val[node] ;
	int mid = (l + r) >> 1 ;
	int x = query(node << 1 , l , mid , from , to) ;
	int y = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return max(x , y) ;
}

int ans[MAX] ;

void solve()
{
	build(1 , 1 , n) ;
	for(int i = 0 ; i <= n+1 ; ++i)
		ins[i].clear() , del[i].clear() , queries[i].clear() ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int idx = min(n+1 , i + a[i]) ;
		ins[idx].push_back(i) ;
		idx = min(n+1 , i + b[i] + 1) ;
		del[idx].push_back(i) ;
	}
	for(int i = 1 ; i <= q ; ++i)
		queries[R[i]].emplace_back(L[i] , i) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(auto &idx : del[i])
			update(1 , 1 , n , idx , -1e9 - 10) ;
		for(auto &idx : ins[i])
			update(1 , 1 , n , idx , -1 * arr[idx]) ;
		int l = max(1 , i-b[i]) , r = i-a[i] ;
		update2(1 , 1 , n , l , r , arr[i]) ;
		for(auto &p : queries[i])
			ans[p.second] = max(ans[p.second] , query(1 , 1 , n , p.first , i)) ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i]>>a[i]>>b[i] ;
	cin>>q ;
	for(int i = 1 ; i <= q ; ++i)
	{
		cin>>L[i]>>R[i] ;
		ans[i] = -1 ;
	}
	solve() ;
	for(int i = 1 ; n-i+1 > i ; ++i)
		swap(arr[i] , arr[n-i+1]) , swap(a[i] , a[n-i+1]) , swap(b[i] , b[n-i+1]) ;
	for(int i = 1 ; i <= q ; ++i)
	{
		int l = n-R[i]+1 , r = n-L[i]+1 ;
		L[i] = l , R[i] = r ;
	}
	solve() ;
	for(int i = 1 ; i <= q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}		

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