Submission #419788

#	Time	Username	Problem	Language	Result	Execution time	Memory
419788		MohamedAhmed04	Teams (IOI15_teams)	C++14	0 / 100	947 ms	143336 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
//#include "grader.cpp"

using namespace std ;

const int MAX = 5e5 + 10 ;

vector<int>tree[4 * MAX] , v[MAX] ;

int n ;

void build(int node , int l , int r)
{
	if(l == r)
	{
		tree[node] = v[l] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid+1 , r) ;
	merge(tree[node << 1].begin() , tree[node << 1].end() , tree[node << 1 | 1].begin() , tree[node << 1 | 1].end() , back_inserter(tree[node])) ;
}

int query(int node , int l , int r , int from , int to , int a , int b)
{
	if(from > r || to < l)
		return 0 ;
	if(l >= from && r <= to)
	{
		int x = upper_bound(tree[node].begin() , tree[node].end() , b) - tree[node].begin() ;
		x -= lower_bound(tree[node].begin() , tree[node].end() , a) - tree[node].begin() ;
		return x ;
	}
	int mid = (l + r) >> 1 ;
	int x = query(node << 1 , l , mid , from , to , a , b) ;
	int y = query(node << 1 | 1 , mid+1 , r , from , to , a , b) ;
	return (x + y) ;
}

void init(int N, int A[], int B[]) 
{
	n = N ;
	for(int i = 0 ; i < n ; ++i)
		v[A[i]].push_back(B[i]) ;
	for(int i = 1 ; i <= n ; ++i)
		sort(v[i].begin() , v[i].end()) ;
	build(1 , 1 , n) ;
}

int can(int m, int K[]) 
{
	sort(K , K + m) ;
	long long now = 0 ;
	for(int i = 0 ; i < m ; ++i)
	{
		int to = 1e9 ;
		if(i+1 < m)
			to = K[i+1] - 1 ;
		now += K[i] - query(1 , 1 , n , 1 , K[i] , K[i] , to) ;
		now = max(now , 0ll) ;
	}
	return (now == 0) ;
}

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int, int, int)':
teams.cpp:32:66: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   32 |   int x = upper_bound(tree[node].begin() , tree[node].end() , b) - tree[node].begin() ;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
teams.cpp:33:82: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   33 |   x -= lower_bound(tree[node].begin() , tree[node].end() , a) - tree[node].begin() ;
      |                                                                                  ^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23