Submission #408847

#	Time	Username	Problem	Language	Result	Execution time	Memory
408847		MohamedAhmed04	New Home (APIO18_new_home)	C++14	100 / 100	4502 ms	178784 KiB

new_home

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

#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 3e5 + 10 ;

int ans[MAX] ;
int n , k , q ;

multiset<int>s[MAX] ;

vector<int>v ;
vector< array<int , 4> >queries ;

int tree[4 * MAX] ;
multiset<int>vals[4 * MAX] ;

void update(int node , int l , int r , int idx , int val)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		if(val < 0)
			vals[node].erase(vals[node].find(-1 * val)) ;
		else
			vals[node].insert(val) ;
		if(vals[node].size())
			tree[node] = *vals[node].rbegin() ;
		else
			tree[node] = 0 ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , val) ;
	update(node << 1 | 1 , mid+1 , r , idx , val) ;
	tree[node] = max(tree[node << 1]  , tree[node << 1 | 1]) ;
}

int query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return 0 ;
	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) ;
}

bool cmp(array<int , 4>&a , array<int , 4>&b)
{
	if(a[0] != b[0])
		return a[0] < b[0] ;
	else
		return a[3] < b[3] ;
}

int getidx(int x)
{
	return lower_bound(v.begin() , v.end() , x) - v.begin() ;
}

void Add(int x , int t)
{
	int prv = *prev(s[t].lower_bound(x)) ;
	int nxt = *s[t].lower_bound(x) ;
	update(1 , 0 , n , getidx(prv) , -1 * nxt) ;
	update(1 , 0 , n , getidx(prv) , x) ;
	update(1 , 0 , n , getidx(x) , nxt) ;
	s[t].insert(x) ;
}

void Erase(int x , int t)
{
	s[t].erase(s[t].find(x)) ;
	int prv = *prev(s[t].lower_bound(x)) ;
	int nxt = *s[t].lower_bound(x) ;
	update(1 , 0 , n , getidx(prv) , -1 * x) ;
	update(1 , 0 , n , getidx(prv) , nxt) ;
	update(1 , 0 , n , getidx(x) , -1 * nxt) ;
}

bool check(int x , int y)
{
	int idx = lower_bound(v.begin() , v.end() , x - y) - v.begin() ;
	idx-- ;
	idx = max(idx , 0) ;
	return (query(1 , 0 , n , 0 , idx) <= x + y) ;
}

int solve(int x)
{
	int l = 0 , r = 1e8 ;
	int ans = -1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(check(x , mid))
			ans = mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k>>q ;
	for(int i = 0 ; i < n ; ++i)
	{
		int x , t , a , b ;
		cin>>x>>t>>a>>b ;
		queries.push_back({a , x , t , 0}) ;
		queries.push_back({b+1 , x , t , -1}) ;
		v.push_back(x) ;
	}
	for(int i = 0 ; i < q ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		queries.push_back({y , x , i , 1}) ;
	}
	v.push_back(0) ;
	sort(v.begin() , v.end()) ;
	v.erase(unique(v.begin() , v.end()) , v.end()) ;
	sort(queries.begin() , queries.end() , cmp) ;
	for(int i = 1 ; i <= k ; ++i)
		s[i].insert(0) , s[i].insert(inf) , update(1 , 0 , n , 0 , inf) ;
	for(auto &a : queries)
	{
		if(a[3] == 0)
			Add(a[1] , a[2]) ;
		else if(a[3] == -1)
			Erase(a[1] , a[2]) ;
		else
			ans[a[2]] = solve(a[1]) ;
	}
	for(int i = 0 ; i < q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}		

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20