oj.uz

Submission #829524

# Submission time Handle Problem Language Result Execution time Memory
829524 2023-08-18T12:01:41 Z MohamedAhmed04 Two Antennas (JOI19_antennas) C++14
0 / 100
 30 ms 17100 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 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 > 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Incorrect 3 ms 7380 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Incorrect 3 ms 7380 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 17100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Incorrect 3 ms 7380 KB Output isn't correct
12 Halted 0 ms 0 KB -