Submission #568038

#	Time	Username	Problem	Language	Result	Execution time	Memory
568038		MohamedAhmed04	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	6238 ms	274832 KiB

Main

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

int tree[2][2 * MAX + 100] ;
int val[2][MAX] ;

int tmp[2] = {(int)1e9 , (int)-1e9} ;

void build(bool t)
{
	for(int i = 2*MAX ; i >= 0 ; --i)
		tree[t][i] = tmp[t] ;
}

void update(int idx , int val , bool t)
{
	for(tree[t][idx += MAX] = val ; idx > 1 ; idx >>= 1)
	{
		if(!t)
			tree[t][idx >> 1] = min(tree[t][idx] , tree[t][idx^1]) ;
		else
			tree[t][idx >> 1] = max(tree[t][idx] , tree[t][idx^1]) ;
	}
}

int query(int l , int r , bool t)
{
	++r ;
	int ans = tmp[t] ;
	for(l += MAX , r += MAX ; l < r ; l >>= 1 , r >>= 1)
	{
		if(l & 1)
		{
			if(!t)
				ans = min(ans , tree[t][l++]) ;
			else
				ans = max(ans , tree[t][l++]) ;
		}
		if(r & 1)
		{
			if(!t)
				ans = min(ans , tree[t][--r]) ;
			else
				ans = max(ans , tree[t][--r]) ;
		}
	}
	return ans ;
}

int q ;

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

pair<int , int>calc(int l , int r)
{
	pair<int , int>p = {r-l , r-l} ;
	if(tree[0][1] <= l)
	{
		int x = query(1 , l , 1) ;
		p = min(p , make_pair(0 , r - x)) ;
	}
	if(tree[1][1] >= r)
	{
		int x = query(r , MAX , 0) ;
		p = min(p , make_pair(0 , x - l)) ;
	}
	if(p.first)
	{
		int x = val[1][tree[0][1]] ;
		p = min(p , make_pair(tree[0][1] - l , r - x)) ;

		x = val[0][tree[1][1]] ;
		p = min(p , make_pair(r - tree[1][1] , x - l)) ;
	}
	return p ;
}

char c[MAX] ;
int L[MAX] , R[MAX] , id[MAX] ;
int ans[MAX] ;

vector< pair<int , int> >tree2[2 * MAX] ;

void Add(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return ;
	if(l >= from && r <= to)
	{
		tree2[node].emplace_back(L[from] , R[from]) ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	Add(node << 1 , l , mid , from , to) ;
	Add(node << 1 | 1 , mid+1 , r , from , to) ;
}

void solve(int node , int st , int en , pair<int , int>best)
{
	if(st > en)
		return ;
	pair<int , int>best2 = best ;
	for(auto &p : tree2[node])
	{
		int l = p.first , r = p.second ;
		sl[l].insert(r) ;
		sr[r].insert(l) ;
		int x = val[0][l] , y = val[1][r] ;
		val[0][l] = *sl[l].begin() , val[1][r] = *sr[r].rbegin() ;
		if(x != val[0][l])
			update(l , val[0][l] , 0) ;
		if(y != val[1][r]) 
			update(r , val[1][r] , 1) ;
		best2 = min(best2 , calc(l , r)) ;
	}
	int mid = (st + en) >> 1 ;
	if(st == en)
		ans[st] = best2.second ;
	else
		solve(node << 1 , st , mid , best2) , solve(node << 1 | 1 , mid+1 , en , best2) ;
	for(auto &p : tree2[node])
	{
		int l = p.first , r = p.second ;
		sl[l].erase(r) ;
		sr[r].erase(l) ;
		int x = val[0][l] , y = val[1][r] ;
		val[0][l] = tmp[0] ;
		if(sl[l].size())
			val[0][l] = *sl[l].begin() ;
		val[1][r] = tmp[1] ;
		if(sr[r].size())
			val[1][r] = *sr[r].rbegin() ;
		if(x != val[0][l])
			update(l , val[0][l] , 0) ;
		if(y != val[1][r])
			update(r , val[1][r] , 1) ;
	}
}

void pre_id()
{
	vector< pair<int , int> >vp ;
	for(int i = 1 ; i <= q ; ++i)
		vp.emplace_back(L[i] , R[i]) ;
	sort(vp.begin() , vp.end()) ;
	vp.erase(unique(vp.begin() , vp.end()) , vp.end()) ;
	for(int i = 1 ; i <= q ; ++i)
	{
		id[i] = lower_bound(vp.begin() , vp.end() , make_pair(L[i] , R[i])) - vp.begin() ;
		id[i]++ ;
	}
}

int freq[MAX] , prv[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	build(0) , build(1) ;
	cin>>q ;
	for(int i = 1 ; i <= q ; ++i)
		cin>>c[i]>>L[i]>>R[i] ;
	pre_id() ;
	for(int i = 1 ; i <= q ; ++i)
	{
		if(c[i] == 'A')
		{
			if(!freq[id[i]])
				prv[id[i]] = i ;
			freq[id[i]]++ ;
		}
		else if(c[i] == 'R')
		{
			freq[id[i]]-- ;
			if(!freq[id[i]])
				Add(1 , 1 , q , prv[id[i]] , i-1) ;
		}
	}
	for(int i = 1 ; i <= q ; ++i)
	{
		if(freq[id[i]])
		{
			Add(1 , 1 , q , prv[id[i]] , q) ;
			freq[id[i]] = 0 ;
		}
	}
	solve(1 , 1 , q , {2e9 , 2e9}) ;
	for(int i = 1 ; i <= q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}		

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