oj.uz

Submission #743677

# Submission time Handle Problem Language Result Execution time Memory
743677 2023-05-17T17:06:49 Z MohamedAhmed04 Akcija (COCI21_akcija) C++14
30 / 110
 14 ms 8500 KB 
#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 ;
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 472 KB Output is correct
9 Correct 3 ms 452 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 472 KB Output is correct
9 Correct 3 ms 452 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 4 ms 608 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 380 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 508 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8500 KB Output is correct
2 Incorrect 12 ms 8332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 472 KB Output is correct
9 Correct 3 ms 452 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 4 ms 608 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 380 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 508 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 4 ms 596 KB Output isn't correct
28 Halted 0 ms 0 KB -