oj.uz

Submission #28060

# Submission time Handle Problem Language Result Execution time Memory
28060 2017-07-15T06:46:22 Z noobprogrammer Teams (IOI15_teams) C++14
100 / 100
 1976 ms 145560 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[10000010] , r[10000010] , n , qs[500010] , rt[500010] , ncnt = 1 ;
vii srt , stk , srt2 ; 

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 } ) ; 
		srt2.push_back({A[i] , 1}) ; srt2.push_back( { B[i] + 1 , -1} ) ;
	}
	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 ;
			}
			// if(from < 0 || stk[j].se < 0) printf("%d",1/0);
			lst = stk[j].fi ;
			mn += stk[j].se ;
			// printf("---> %d : %d %d\n" , j , stk[j].fi , stk[j].se) ; 
		}
		// printf("%d : %d %d\n" , i , mn , qs[num]) ;
		if(qs[num] - mn < sz) return 0 ;
	}

	return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:54: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 123120 KB Output is correct
2 Correct 0 ms 123120 KB Output is correct
3 Correct 0 ms 123120 KB Output is correct
4 Correct 0 ms 123120 KB Output is correct
5 Correct 0 ms 123120 KB Output is correct
6 Correct 0 ms 123120 KB Output is correct
7 Correct 0 ms 123120 KB Output is correct
8 Correct 0 ms 123120 KB Output is correct
9 Correct 0 ms 123120 KB Output is correct
10 Correct 0 ms 123120 KB Output is correct
11 Correct 0 ms 123120 KB Output is correct
12 Correct 0 ms 123120 KB Output is correct
13 Correct 0 ms 123120 KB Output is correct
14 Correct 0 ms 123120 KB Output is correct
15 Correct 0 ms 123120 KB Output is correct
16 Correct 0 ms 123120 KB Output is correct
17 Correct 0 ms 123120 KB Output is correct
18 Correct 0 ms 123120 KB Output is correct
19 Correct 0 ms 123120 KB Output is correct
20 Correct 0 ms 123120 KB Output is correct
21 Correct 0 ms 123120 KB Output is correct
22 Correct 0 ms 123120 KB Output is correct
23 Correct 0 ms 123120 KB Output is correct
24 Correct 0 ms 123120 KB Output is correct
25 Correct 0 ms 123120 KB Output is correct
26 Correct 0 ms 123120 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 128172 KB Output is correct
2 Correct 56 ms 128172 KB Output is correct
3 Correct 59 ms 128172 KB Output is correct
4 Correct 76 ms 128172 KB Output is correct
5 Correct 39 ms 128172 KB Output is correct
6 Correct 36 ms 128172 KB Output is correct
7 Correct 36 ms 128172 KB Output is correct
8 Correct 43 ms 128172 KB Output is correct
9 Correct 9 ms 128172 KB Output is correct
10 Correct 23 ms 128172 KB Output is correct
11 Correct 19 ms 128172 KB Output is correct
12 Correct 23 ms 128172 KB Output is correct
13 Correct 39 ms 128172 KB Output is correct
14 Correct 23 ms 128172 KB Output is correct
15 Correct 73 ms 128172 KB Output is correct
16 Correct 36 ms 128172 KB Output is correct
17 Correct 33 ms 128172 KB Output is correct
18 Correct 29 ms 128172 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 128172 KB Output is correct
2 Correct 89 ms 128172 KB Output is correct
3 Correct 113 ms 130180 KB Output is correct
4 Correct 103 ms 128172 KB Output is correct
5 Correct 76 ms 128172 KB Output is correct
6 Correct 53 ms 128172 KB Output is correct
7 Correct 49 ms 128172 KB Output is correct
8 Correct 59 ms 128172 KB Output is correct
9 Correct 13 ms 128172 KB Output is correct
10 Correct 19 ms 128172 KB Output is correct
11 Correct 53 ms 128172 KB Output is correct
12 Correct 643 ms 128172 KB Output is correct
13 Correct 163 ms 128172 KB Output is correct
14 Correct 153 ms 128860 KB Output is correct
15 Correct 79 ms 128172 KB Output is correct
16 Correct 79 ms 128172 KB Output is correct
17 Correct 53 ms 128172 KB Output is correct
18 Correct 39 ms 128172 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 143588 KB Output is correct
2 Correct 586 ms 143588 KB Output is correct
3 Correct 679 ms 145560 KB Output is correct
4 Correct 596 ms 143588 KB Output is correct
5 Correct 343 ms 143588 KB Output is correct
6 Correct 299 ms 143588 KB Output is correct
7 Correct 233 ms 143588 KB Output is correct
8 Correct 286 ms 143588 KB Output is correct
9 Correct 53 ms 143588 KB Output is correct
10 Correct 136 ms 143588 KB Output is correct
11 Correct 1216 ms 143588 KB Output is correct
12 Correct 1976 ms 143588 KB Output is correct
13 Correct 953 ms 143588 KB Output is correct
14 Correct 606 ms 143588 KB Output is correct
15 Correct 453 ms 143588 KB Output is correct
16 Correct 433 ms 143588 KB Output is correct
17 Correct 176 ms 143588 KB Output is correct
18 Correct 196 ms 143588 KB Output is correct