Submission #743687

#	Time	Username	Problem	Language	Result	Execution time	Memory
743687		MohamedAhmed04	Akcija (COCI21_akcija)	C++14	110 / 110	1613 ms	32296 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2004 ;

int arr[MAX] ;
int n , k ;

vector< pair<int , int> >vp ;
int w[MAX] , d[MAX] ;

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 update(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 ;
	update(node << 1 , l , mid , from , to , val) ;
	update(node << 1 | 1 , mid+1 , r , from , to , val) ;
	tree[node] = min(tree[node << 1] , tree[node << 1 | 1]) ;
}

int FindIdx(int node , int l , int r)
{
	if(tree[node] != 0)
		return 0 ;
	if(l == r)
		return l ;
	int mid = (l + r) >> 1 ;
	prop(node << 1 , l , mid) ;
	prop(node << 1 | 1 , mid+1 , r) ;
	if(!tree[node << 1 | 1])
		return FindIdx(node << 1 | 1 , mid+1 , r) ;
	else
		return FindIdx(node << 1 , l , mid) ;
}

int state[MAX][MAX] ; //0 -> must be out, 1 -> must be in, 2 -> out and can be in, 3 -> in and can be out
int suff[MAX] ;
priority_queue< array<long long , 5> >q ;


void Insert_States(int cur , int prv , int idx1 , int idx2)
{
	memset(tree , 0 , sizeof(tree)) ;
	memset(lazy , 0 , sizeof(lazy)) ;
	memset(suff , -1 , sizeof(suff)) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		state[cur][i] = state[prv][i] ;
		if(i < idx1 && state[cur][i] == 3)
			state[cur][i] = 1 ;
	}
	int sz = 0 ;
	long long sum = 0 ;
	state[cur][idx1] = 0 , state[cur][idx2] = 3 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		update(1 , 1 , n , i , n , 1) ;
		if(state[cur][i] == 1 || state[cur][i] == 3)
			++sz , sum += w[i] , update(1 , 1 , n , d[i] , n , -1) ;
		if(state[cur][i] == 2)
		{
			if(suff[d[i]] == -1)
				suff[d[i]] = i ;
			else if(w[i] < w[suff[d[i]]])
				suff[d[i]] = i ;
		}
	}
	for(int i = n-1 ; i >= 1 ; --i)
	{
		if(suff[i+1] == -1)
			continue ;
		if(suff[i] == -1 || w[suff[i+1]] < w[suff[i]])
			suff[i] = suff[i+1] ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		if(state[cur][i] != 3)
			continue ;
		update(1 , 1 , n , d[i] , n , 1) ;
		int idx = FindIdx(1 , 1 , n) + 1 ;
		if(suff[idx] != -1)
		{
			idx = suff[idx] ;
			q.push({sz , -1 * (sum - w[i] + w[idx]) , cur , i , idx}) ;
		}
		else
			q.push({sz-1 , -1 * (sum - w[i]) , cur , i , 0}) ;
		update(1 , 1 , n , d[i] , n , -1) ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int w , d ;
		cin>>w>>d ;
		vp.emplace_back(w , d) ;
	}
	sort(vp.begin() , vp.end()) ;
	for(int i = 1 ; i <= n ; ++i)
		w[i] = vp[i-1].first , d[i] = vp[i-1].second ;
	for(int i = 1 ; i <= n ; ++i)
		update(1 , 1 , n , i , n , 1) ;
	int sz = 0 ;
	long long sum = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		state[1][i] = 2 ;
		update(1 , 1 , n , d[i] , n , -1) ;
		if(tree[1] >= 0)
			state[1][i] = 3 , ++sz , sum += w[i] ;
		else
			update(1 , 1 , n , d[i] , n , 1) ;
	}
	q.push({sz , -1 * sum , 1 , 0 , 0}) ;
	for(int i = 1 ; i <= k ; ++i)
	{
		array<long long , 5>ans = q.top() ;
		q.pop() ;
		cout<<ans[0]<<" "<<-1ll * ans[1]<<"\n" ;
		Insert_States(i , ans[2] , ans[3] , ans[4]) ;
	}
	return 0 ;
}		

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 20 / 20