oj.uz

Submission #28051

# Submission time Handle Problem Language Result Execution time Memory
28051 2017-07-15T06:11:51 Z noobprogrammer Teams (IOI15_teams) C++14
21 / 100
 626 ms 102256 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std ;
#define ii pair<int,int>
#define fi first 
#define se second 
#define vi vector<int>
#define vii vector<ii>
typedef long long ll ;

int st[10000010] , le[1000010] , r[10000010] , n , qs[500010] , rt[500010] , ncnt = 1 ;
vii srt , stk ; 

void upd(int prev , int node , int f , int l ,int x){
	if(f == l){
		st[node] = st[prev] + 1 ;
		return ;
	}
	int mid = (f+l)>>1 ;
	if(mid < x){
		le[node] = le[prev] ; r[node] = ncnt++ ;
		upd( r[prev] , r[node] , mid+1 , l , x ) ;
	}
	else{
		le[node] = ncnt++ ; r[node] = r[prev] ;
		upd( le[prev] , le[node] , f , mid , x ) ;	
	}
	st[node] = st[le[node]] + st[r[node]] ;
}

int qr(int prev , int node , int f ,int l , int x ){
	if(x == 0) return 0 ;
	if(x >= l) return st[node] - st[prev] ;
	int mid = (f+l)>>1 ;
	if(mid < x) return st[le[node]] - st[le[prev]] + qr(r[prev] , r[node] , mid+1 , l , x ) ;
	else return qr(le[prev] , le[node] , f , mid , x ) ;
}

void init(int N, int A[], int B[]) {
	n = N ; 
	for(int i=0;i<n;i++) {
		qs[A[i]]++ ; qs[B[i]+1]-- ;
		srt.push_back( { B[i] + 1 , i } ) ; 
	}
	sort(srt.begin() , srt.end() ) ;
	for(int i=1;i<=n;i++) qs[i] += qs[i-1] ;
	 // printf("%d ", qs[i]) ;
	// cout << endl ; 
	int j = 0 , tmp , num ; 
	rt[0] = 0 ;
	for(int i=1;i<=n;i++){
		rt[i] = rt[i-1] ; 
		while( j<srt.size() && i >= srt[j].fi ) {
			// printf("%d %d\n" , srt[j].fi , srt[j].se) ;
			num = srt[j].se ;
			tmp = ncnt++ ;
			upd(rt[i] , tmp , 1 , n , A[num] ) ;
			rt[i] = tmp ; 
			j++ ;
		}
		// for(int j=1 ; j<=n ;j++) printf("%d " , qr(rt[i-1] , rt[i] , 1 , n , j) ) ;
		// cout << endl ;
	}
}

int can(int m, int arr[]) {
	int sum = 0 ;
	for(int i=0;i<m;i++) {
		sum += arr[i] ;
		if(sum > n) return 0 ; 
	}
	sort(arr , arr+m) ;
	int j ; 
	sum = 0 ;
	stk.clear() ; 
	// printf("--------\n") ;

	for(int i=0;i<m;){
		j = i ; sum = 0 ;
		while(j<m && arr[j] == arr[i]){
			sum += arr[j] ;
			j++ ;
		}
		stk.push_back({arr[i] , sum});
		i = j ;
	}
	int lst = 0 , mn = 0 , from = 0 , num , sz , prev , nw , cur ;
	// printf("--------\n") ;
	for(int i=0;i<stk.size();i++){
		from = 0 ; lst = 0 ; mn = 0 ;
		num = stk[i].fi ; sz = stk[i].se ; 
		if(i > 0 ) prev = stk[i-1].fi ;
		// printf("%d : %d %d\n" , i , num ,sz) ;
		for(j=0;j<i;j++){
			if(stk[j].se == 0) continue ;
			cur = stk[j].fi ;
			nw = qr(rt[prev] , rt[num] , 1 , n , cur) - qr(rt[prev] , rt[num] , 1 , n , lst) ;
			if(nw + from >= stk[j].se){
				nw -= stk[j].se ;
				stk[j].se = 0 ;
				from += nw ; 
			}
			else{
				stk[j].se -= (nw + from) ;
				from = 0 ;
			}
			lst = stk[j].fi ;
			mn += stk[j].se ;
			// printf("---> %d : %d %d\n" , j , stk[j].fi , stk[j].se) ; 
		}
		if(qs[num] - mn < sz) return 0 ;
	}

	return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while( j<srt.size() && i >= srt[j].fi ) {
           ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:89:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<stk.size();i++){
               ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 87964 KB Output is correct
2 Correct 0 ms 87964 KB Output is correct
3 Correct 0 ms 87964 KB Output is correct
4 Correct 0 ms 87964 KB Output is correct
5 Correct 0 ms 87964 KB Output is correct
6 Correct 0 ms 87964 KB Output is correct
7 Correct 0 ms 87964 KB Output is correct
8 Correct 0 ms 87964 KB Output is correct
9 Correct 0 ms 87964 KB Output is correct
10 Correct 0 ms 87964 KB Output is correct
11 Correct 0 ms 87964 KB Output is correct
12 Correct 0 ms 87964 KB Output is correct
13 Correct 0 ms 87964 KB Output is correct
14 Correct 0 ms 87964 KB Output is correct
15 Correct 0 ms 87964 KB Output is correct
16 Correct 0 ms 87964 KB Output is correct
17 Correct 0 ms 87964 KB Output is correct
18 Correct 0 ms 87964 KB Output is correct
19 Correct 0 ms 87964 KB Output is correct
20 Correct 0 ms 87964 KB Output is correct
21 Correct 0 ms 87964 KB Output is correct
22 Correct 0 ms 87964 KB Output is correct
23 Correct 0 ms 87964 KB Output is correct
24 Correct 0 ms 87964 KB Output is correct
25 Correct 0 ms 87964 KB Output is correct
26 Correct 0 ms 87964 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 90368 KB Output is correct
2 Correct 76 ms 90368 KB Output is correct
3 Correct 76 ms 90368 KB Output is correct
4 Correct 83 ms 90368 KB Output is correct
5 Incorrect 26 ms 90368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 90368 KB Output is correct
2 Correct 76 ms 90368 KB Output is correct
3 Correct 86 ms 92888 KB Output is correct
4 Correct 79 ms 90368 KB Output is correct
5 Incorrect 46 ms 90368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 98104 KB Output is correct
2 Correct 626 ms 98104 KB Output is correct
3 Correct 606 ms 102256 KB Output is correct
4 Correct 366 ms 98104 KB Output is correct
5 Incorrect 166 ms 98104 KB Output isn't correct
6 Halted 0 ms 0 KB -