oj.uz

답안 #829527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
829527 2023-08-18T12:02:26 Z MohamedAhmed04 Two Antennas (JOI19_antennas) C++14
0 / 100
 392 ms 34048 KB 
#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 > 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 6 ms 14420 KB Output is correct
8 Correct 6 ms 14448 KB Output is correct
9 Correct 6 ms 14420 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Incorrect 6 ms 14420 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 6 ms 14420 KB Output is correct
8 Correct 6 ms 14448 KB Output is correct
9 Correct 6 ms 14420 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Incorrect 6 ms 14420 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 30260 KB Output is correct
2 Correct 291 ms 34048 KB Output is correct
3 Correct 251 ms 29988 KB Output is correct
4 Correct 376 ms 34044 KB Output is correct
5 Correct 152 ms 23496 KB Output is correct
6 Correct 392 ms 33976 KB Output is correct
7 Correct 306 ms 32148 KB Output is correct
8 Correct 291 ms 34040 KB Output is correct
9 Correct 58 ms 17216 KB Output is correct
10 Correct 372 ms 34004 KB Output is correct
11 Correct 182 ms 25764 KB Output is correct
12 Correct 391 ms 33992 KB Output is correct
13 Incorrect 239 ms 31656 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14420 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 6 ms 14420 KB Output is correct
8 Correct 6 ms 14448 KB Output is correct
9 Correct 6 ms 14420 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Incorrect 6 ms 14420 KB Output isn't correct
12 Halted 0 ms 0 KB -