oj.uz

Submission #605153

# Submission time Handle Problem Language Result Execution time Memory
605153 2022-07-25T13:29:48 Z MohamedAhmed04 Team Contest (JOI22_team) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX][3] ;
int n ;

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

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

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

int query(int node , int l , int r , int from , int to)
{
	prop(node , l , r) ;
	if(from > r || to < l)
		return (-1e9) ;
	if(l >= from && r <= to)
		return tree[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 tree2[4 * MAX] ;

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

int FindFirst(int node , int l , int r , int val)
{
	if(val > tree2[node])
		return (n+1) ;
	if(l == r)
		return l ;
	int mid = (l + r) >> 1 ;
	if(tree2[mid] > val)
		return FindFirst(node << 1 , l , mid , val) ;
	else
		return FindFirst(node << 1 | 1 , mid+1 , r , val) ;
}

int pos[MAX] , nxt[MAX] ;

set<int>s ;

vector< array<int , 3> >v ;
vector< pair<int , int> >vp ;

void Insert(int idx)
{
	update(1 , 1 , n , idx , -1e9) ;
	s.insert(idx) ;
	int nxtmx = FindFirst(1 , 1 , n , v[idx][1]) ;
	int l = nxt[idx] , r = nxtmx-1 ;
	if(l <= r)
		Add(1 , 1 , n , l , r , v[idx][1]) ;
}

void Erase(int idx)
{
	s.erase(idx) ;
	int nxtmx = FindFirst(1 , 1 , n , v[idx][1]) ;
	int l = nxt[idx] , r = nxtmx-1 ;
	if(l <= r)
		Add(1 , 1 , n , l , r , -1 * v[idx][1]) ;
}

void Del(int idx)
{
	int prv = -1 ;
	if((*s.begin()) != idx)
	{
		prv = *prev(s.lower_bound(idx)) ;
		Erase(prv) ;
	}
	Erase(idx) ;
	update(1 , 1 , n , idx , -1e9) ;
	int cur = prv ;
	if(cur == -1)
		cur = FindFirst(1 , 1 , n , 0) ;
	while(s.find(cur) != s.end())
	{
		Insert(cur) ;
		cur = FindFirst(1 , 1 , n , v[cur][1]) ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i][0]>>arr[i][1]>>arr[i][2] ;
	for(int i = 1 ; i <= n ; ++i)
		v.push_back({arr[i][1] , arr[i][2] , i}) , vp.emplace_back(arr[i][0] , i) ;
	v.push_back({0 , 0 , 0}) , vp.emplace_back(0 , 0) ;
	sort(v.begin() , v.end()) ;
	sort(vp.begin() , vp.end()) ;

	nxt[n] = n+1 ;
	for(int i = n-1 ; i >= 1 ; --i)
	{
		nxt[i] = nxt[i+1] ;
		if(v[i][0] != v[i+1][0])
			nxt[i] = i+1 ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		Add(1 , 1 , n , i , i , v[i][0]) ;
		update(1 , 1 , n , i , v[i][1]) ;
	}
	int Max = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		// if(query(1 , 1 , n , i , i) == v[i][0])
		// 	Add(1 , 1 , n , i , i , -1e9) ;
		if(v[i][1] <= Max)
			continue ;
		Max = v[i][1] ;
		Insert(i) ; 
	}
	int j = n , ans = -1 ; 
	for(int i = n ; i >= 1 ; --i)
	{
		int idx = vp[i].second ;
		while(j >= 0 && vp[i].first == vp[j].first)
			Erase(j) , --j ;
		int l = FindFirst(1 , 1 , n , arr[idx][2]) ;
		l = max(l , nxt[pos[idx]]) ;
		if(l <= n)
			ans = max(ans , vp[i].first + query(1 , 1 , n , l , n)) ;
	}
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -