Submission #568151

#	Time	Username	Problem	Language	Result	Execution time	Memory
568151		MohamedAhmed04	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	2571 ms	248116 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

struct Node
{
	int l , r , Min ;
};

int arr[MAX] ;
int n , q ;
Node tree[4 * MAX] ;

int val[2][MAX] ;

multiset<int>sl[MAX] , sr[MAX] ;

Node Merge(Node &a , Node &b)
{
	Node c ;
	c.l = max(a.l , b.l) ;
	c.r = min(a.r , b.r) ;
	c.Min = min({a.Min , b.Min , b.r - a.l}) ;
	return c ;
}

void update(int node , int l , int r , int idx)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[node].l = val[0][l] , tree[node].r = val[1][l] ;
		tree[node].Min = tree[node].r - tree[node].l ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx) ;
	update(node << 1 | 1 , mid+1 , r , idx) ;
	tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
}

multiset<int>L , R ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	for(int i = 1 ; i < 4 * MAX ; ++i)
		tree[i].l = -1e9 , tree[i].r = 1e9 , tree[i].Min = 2e9 ;
	for(int i = 1 ; i < MAX ; ++i)
		val[0][i] = -1e9 , val[1][i] = 1e9 ;
	cin>>q ;
	while(q--)
	{
		char c ;
		cin>>c ;
		if(c == 'A')
		{
			int l , r ;
			cin>>l>>r ;
			L.insert(l) , R.insert(r) ;
			sl[l].insert(r) ;
			sr[r].insert(l) ;
			val[1][l] = *sl[l].begin() , val[0][r] = *sr[r].rbegin() ;
			update(1 , 1 , MAX , l) , update(1 , 1 , MAX , r) ;
		}
		else if(c == 'R')
		{
			int l , r ;
			cin>>l>>r ;
			L.erase(L.find(l)) , R.erase(R.find(r)) ;
			sl[l].erase(sl[l].find(r)) ;
			sr[r].erase(sr[r].find(l)) ;
			val[1][l] = 1e9 , val[0][r] = -1e9 ;
			if(sl[l].size())
				val[1][l] = *sl[l].begin() ;
			if(sr[r].size())
				val[0][r] = *sr[r].rbegin() ;
			update(1 , 1 , MAX , l) , update(1 , 1 , MAX , r) ;
		}
		int x = *L.rbegin() , y = *R.begin() ;
		if(y > x)
			cout<<(*sl[x].begin()) - (*sr[y].rbegin())<<"\n" ;
		else
			cout<<tree[1].Min<<"\n" ;
	}
	return 0 ;
}		

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3